fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define gc getchar_unlocked
  4. #define fo(i,n) for(i=0;i<n;i++)
  5. #define Fo(i,k,n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
  6. #define ll long long
  7. #define si(x)	scanf("%d",&x)
  8. #define sl(x)	scanf("%lld",&x)
  9. #define ss(s)	scanf("%s",s)
  10. #define pi(x)	printf("%d\n",x)
  11. #define pl(x)	printf("%lld\n",x)
  12. #define ps(s)	printf("%s\n",s)
  13. #define pb push_back
  14. #define mp make_pair
  15. #define F first
  16. #define S second
  17. #define all(x) x.begin(), x.end()
  18. #define clr(x) memset(x, 0, sizeof(x))
  19. #define sortall(x) sort(all(x))
  20. #define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
  21. #define PI 3.1415926535897932384626
  22. typedef pair<int, int>	pii;
  23. //typedef pair<ll, ll>	pl;
  24. typedef vector<int>		vi;
  25. typedef vector<ll>		vl;
  26. typedef vector<pii>		vpii;
  27. //typedef vector<pl>		vpl;
  28. typedef vector<vi>		vvi;
  29. typedef vector<vl>		vvl;
  30. int mpow(int base, int exp);
  31. void ipgraph(int n, int m);
  32. void dfs(int u, int par);
  33. const int mod = 1000000007;
  34. const int N = 200003, M = N;
  35. //=======================
  36.  
  37. vi g[N];
  38. vi a;
  39. int n;
  40. const int rtn = 142;
  41. int cnt[N][rtn];
  42. int tot[rtn];
  43. int pl[N], bet[N];
  44. int id(int x){
  45. 	return x/rtn;
  46. }
  47. int solve(int x){
  48.   //  cout<<x<<endl;
  49. 	if(x<0) return -1;
  50. 	int sab = 0;
  51. 	for(int k: a)
  52. 	{
  53. 		sab += cnt[x][k];
  54. 	//	cout<<k<<" ";
  55. 	}
  56. 	//cout<<endl<<sab<<" "<<tot[x]<<endl;
  57. 	if(sab == tot[x]) return solve(x-1);
  58. 	return x;
  59. }
  60. int mark[N], P, LA;
  61. int sol(int x, int w){
  62. 	if(x<0) return LA;
  63. 	int sab = cnt[x][w];
  64. 	if(sab==0) return sol(x-1, w);
  65. 	LA = x;
  66. 	for(int k: a)
  67. 		sab += cnt[x][k];
  68. 	if(sab==tot[x]) return sol(x-1, w);
  69. 	return x;
  70. }
  71. int win(int x){
  72. 	int i = x*rtn, j = min(n-1, i+rtn-1);
  73. 	int w;
  74.  
  75. 	Fo(w, j, i-1){
  76. 		if(!mark[pl[w]]){
  77. 			P = pl[w];
  78. 			return sol(x, P);
  79. 		}
  80. 	}
  81. }
  82.  
  83.  
  84. int main()
  85. {
  86. 	ios_base::sync_with_stdio(false);
  87. 	cin.tie(NULL);
  88. 	int i,k,j,q,x;
  89. 	cin>>n;
  90. 	int B;
  91. 	fo(i, n){
  92. 	    int a, b;
  93. 		cin>>a>>b;
  94. 		pl[i] = a;
  95. 		bet[i] = b;
  96. 		//b[id(i)][a]
  97. 		cnt[id(i)][a]++;
  98. 		tot[id(i)]++;
  99. 		B = id(i);
  100. 	}
  101.  
  102. 	cin>>q;
  103. 	while(q--){
  104. 		cin>>k;
  105.  
  106.  
  107. 		a.clear();
  108. 		fo(i, k) cin>>x, a.pb(x), mark[x] = 1;
  109. 		x = solve(B);
  110. 		if(x==-1){
  111. 			cout<<0<<" "<<0<<endl;
  112. 			for(int x: a) mark[x] = 0;
  113. 			continue;
  114. 		}
  115. 		x = win(x);
  116. 		//x bucket mei P ki last bet
  117. 		int lo = x*rtn, hi = lo+rtn-1;
  118. 		hi = min(n-1, hi);
  119. 		int ans = 0;
  120. 		Fo(i, hi, lo-1){
  121. 			if(mark[pl[i]]) continue;
  122. 			if(pl[i]==P) ans = bet[i];
  123. 			else break;
  124. 		}
  125. 		cout << P<<" "<<ans << endl;
  126. 		for(int x: a) mark[x] = 0;
  127.  
  128. 	}
  129.  
  130.  
  131. 	return 0;
  132. }
  133.  
Success #stdin #stdout 0s 119104KB
comments (?)
stdin
copy 
6
1 10
2 100
3 1000
1 10000
2 100000
3 1000000
3
1 3
2 2 3
2 1 2
stdout
copy 
2 100000
1 10
3 1000
https://ideone.com/tDfEcm
my template :)
language:
C++14 (gcc 8.3)
created:
8 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!