fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define rep(i,a,n) for (int i=a;i<n;i++)
  4. #define per(i,a,n) for (int i=n-1;i>=a;i--)
  5. #define pb push_back
  6. #define mp make_pair
  7. #define all(x) (x).begin(),(x).end()
  8. #define fi first
  9. #define se second
  10. #define SZ(x) ((int)(x).size())
  11. typedef vector<int> VI;
  12. typedef long long ll;
  13. typedef pair<int,int> PII;
  14. mt19937 mrand(random_device{}()); 
  15. const ll mod=1000000007;
  16. int rnd(int x) { return mrand() % x;}
  17. ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
  18. ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
  19. // head
  20.  
  21.  
  22. const int N=101000;
  23. typedef double db;
  24.  
  25. db dp[N],ldp[N];
  26. int p1[N],p2[N];
  27. int sp[N],lsp[N],n;
  28.  
  29. db calc(int x,int y) {
  30. 	db val=dp[x]+dp[y]+min(x,y)+x+y;
  31. 	db bp=0;
  32. 	db pr=1;
  33. 	rep(i,1,x+1) {
  34. 		pr=pr*(x+1-i)/(x+y+1-i);
  35. 		bp+=pr;
  36. 		if (pr<1e-10) break;
  37. 	}
  38. 	pr=1;
  39. 	rep(i,1,y+1) {
  40. 		pr=pr*(y+1-i)/(x+y+1-i);
  41. 		bp+=pr;
  42. 		if (pr<1e-10) break;
  43. 	}
  44. 	val-=bp;
  45. //	printf("%.10f\n",bp);
  46. 	return val;
  47. }
  48.  
  49. db lcalc(int x,int y) {
  50. 	db val=ldp[x]+dp[y]+min(x,y)+x+y-p1[x];
  51. 	db bp=0;
  52. 	db pr=1;
  53. 	rep(i,1,x+1) {
  54. 		pr=pr*(x+1-i)/(x+y+1-i);
  55. 		bp+=pr;
  56. 		if (pr<1e-10) break;
  57. 	}
  58. 	pr=1;
  59. 	rep(i,1,y+1) {
  60. 		pr=pr*(y+1-i)/(x+y+1-i);
  61. 		bp+=pr;
  62. 		if (pr<1e-10) break;
  63. 	}
  64. 	val-=bp;
  65. //	printf("%d %d %d\n",x,y,p1[x]);
  66. 	return val;
  67. }
  68.  
  69. int pans=0;
  70. int cnt[N],perm[N],ins[N],rd[N];
  71. int totQ;
  72.  
  73. int Query(int u) {
  74. 	++totQ;
  75. 	if (ins[u]) {
  76. 		cnt[perm[u]]--;
  77. 		if (cnt[perm[u]]==0) pans--;
  78. 	} else {
  79. 		cnt[perm[u]]++;
  80. 		if (cnt[perm[u]]==1) pans++;
  81. 	}
  82. 	ins[u]^=1;
  83. 	return pans;
  84. }
  85.  
  86. int pre,pins[N];
  87. VI x,y;
  88.  
  89. struct RNG {
  90.     int operator() (int n) {
  91.         return rnd(n);
  92.     }
  93. };
  94.  
  95. void query(int u) {
  96. 	pre=Query(rd[u]);
  97. }
  98.  
  99. bool inside(int u) {
  100. 	int cur=pre;
  101. 	pre=Query(rd[u]);
  102. 	return pre==cur;
  103. }
  104.  
  105. void Answer(int u,int v) {
  106. 	assert(perm[u]==perm[v]);
  107. }
  108.  
  109. void prec(int n) {
  110. 	rep(i,0,2*n) perm[i+1]=i/2;
  111. 	random_shuffle(perm+1,perm+2*n+1);
  112. }
  113.  
  114. int bp=0;
  115.  
  116. void gao(int l,int r,VI c,bool f) {
  117. 	int n=r-l+1,md=0;
  118. 	if (n==1) { Answer(rd[x[l]],rd[c[0]]); return; }
  119. 	if (f) {
  120. 		md=r-sp[n];
  121. 		rep(i,md+1,r+1) query(x[i]);
  122. 	} else {
  123. 		md=l+sp[n]-1;
  124. 		rep(i,l,md+1) query(x[i]);
  125. 	}
  126. 	VI fl,fr;
  127. 	random_shuffle(all(c),RNG());
  128. 	rep(i,0,SZ(c)) {
  129. 		if (SZ(fl)==md-l+1) fr.pb(c[i]);
  130. 		else if (SZ(fr)==r-md) fl.pb(c[i]);
  131. 		else if (l==0&&pins[c[i]]<=md) fl.pb(c[i]);
  132. 		else if (inside(c[i])) fl.pb(c[i]);
  133. 		else fr.pb(c[i]);
  134. 	}
  135. 	gao(l,md,fl,1);
  136. 	gao(md+1,r,fr,0);
  137. }
  138.  
  139. void Solve(int nn) {
  140. 	n=nn;
  141. 	prec(n);
  142. 	rep(i,1,2*n+1) rd[i]=i;
  143. 	random_shuffle(rd+1,rd+2*n+1,RNG());
  144. 	rep(i,1,2*n+1) {
  145. 		if (inside(i)) {
  146. 			pins[i]=SZ(x)-1;
  147. 			p1[SZ(x)]++;
  148. 			p2[SZ(x)]+=1./SZ(x);
  149. 			y.pb(i);
  150. 		} else {
  151. 			x.pb(i);
  152. 		}
  153. 	}
  154. 	rep(i,1,n+1) p1[i]+=p1[i-1];
  155. 	per(i,1,n+1) p2[i]+=p2[i+1];
  156. 	rep(i,2,n+1) {
  157. 		dp[i]=1e9;
  158. 		int pl=max(1,sp[i-1]);
  159. 		db fval=calc(pl,i-pl);
  160. 		while (pl<i/2) {
  161. 			db gval=calc(pl+1,i-pl-1);
  162. 			if (fval>gval) fval=gval,++pl;
  163. 			else break;
  164. 		}
  165. 		dp[i]=fval; sp[i]=pl;
  166. 	}
  167. 	gao(0,n-1,y,1);
  168. 	printf("%d\n",totQ);
  169. }
  170.  
  171. int main() {
  172. 	Solve(44000);
  173. }
Success #stdin #stdout 0.08s 20376KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
995527
https://ideone.com/DmGoZ4
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!