fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define DB(x) cout<<#x<<"="<<x<<endl;
  6. #define MP make_pair
  7.  
  8. typedef long long int64;
  9. typedef pair<int,int> pii;
  10. typedef vector<pii> vi;
  11.  
  12. const int oo = 1<<30;
  13. const double EPS = 1e-9;
  14. const int MAXN = (int)1e6 + 10;
  15.  
  16. vi ady[MAXN];
  17. int DG[MAXN]; // Degree
  18. int ptr[MAXN], X[MAXN], Y[MAXN];
  19. bool mk[MAXN];
  20. char ANS[MAXN];
  21. map<pii, int> M;
  22. stack<int> S;
  23. int edg, mx, my, cnt;
  24.  
  25. void init(int n){
  26. 	edg = cnt = 0;
  27. 	S = stack<int>();
  28. 	M.clear();
  29. 	for (int i = 0; i < n; ++i){
  30. 		ady[i].clear();
  31. 		DG[i] = 0;
  32. 		ptr[i] = 0;
  33. 	}
  34. }
  35.  
  36. void add_edge(int u, int v){
  37. 	if (v < u) swap(u,v);
  38. 	M[ MP(u,v) ] = edg;
  39. 	DG[u]++; DG[v]++;
  40. 	ady[u].push_back( MP(v, edg) );
  41. 	ady[v].push_back( MP(u, edg) );
  42. 	ANS[edg] = 0;
  43. 	X[edg] = u, Y[edg] = v;
  44. 	mk[edg++] = false;
  45. }
  46.  
  47. pii getNx(int s){
  48. 	for (; ptr[s] < (int)ady[s].size(); ++ptr[s]){
  49. 		pii cur = ady[s][ ptr[s] ];
  50. 		if (mk[cur.second]) continue;
  51. 		return cur;
  52. 	}
  53. 	return MP(-1, -1);
  54. }
  55.  
  56. void dfs(int s){
  57. 	for (; ptr[s] < (int)ady[s].size(); ++ptr[s]){
  58. 		pii cur = ady[s][ ptr[s] ];
  59. 		if (mk[cur.second]) continue;
  60. 		mk[cur.second] = true;
  61. 		DG[ X[cur.second] ]--;
  62. 		DG[ Y[cur.second] ]--;
  63. 		dfs(cur.first);
  64. 		break;
  65. 	}
  66. 	S.push(s);
  67. }
  68.  
  69. void make(){
  70. 	if (S.empty()) return;
  71. 	int a = S.top(); S.pop();
  72.  
  73. 	int cur = 0;
  74. 	while (!S.empty()){
  75. 		int b = S.top(); S.pop();
  76.  
  77. 		int u = a, v = b;
  78. 		if (v < u) swap(u, v);
  79.  
  80. 		ANS[M[MP(u,v)]] = 'A' + cur;
  81. 		++cnt;
  82. 		cur ^= 1;
  83. 		a = b;
  84. 	}
  85. }
  86.  
  87. void read1(int n){
  88. 	int x1, y1, ax, bx, ay, by;
  89. 	cin >> x1 >> y1 >> ax >> bx >> mx >> ay >> by >> my;
  90.  
  91. 	init(mx + my);
  92.  
  93. 	for (int i = 0; i < n; ++i){
  94. 		add_edge(x1, mx + y1);
  95. 		x1 = (ax * x1 + bx) % mx;
  96. 		y1 = (ay * y1 + by) % my;
  97. 	}
  98. }
  99.  
  100. void read2(int n)
  101. {
  102. 	cin >> mx >> my;
  103. 	init(mx + my);
  104. 	for (int i = 0; i < n; ++i){
  105. 		int u, v;
  106. 		cin >> u >> v;
  107. 		add_edge(u, v + mx);
  108. 	}
  109. }
  110.  
  111. int main()
  112. {
  113. 	ios_base::sync_with_stdio(0);
  114. 	cin.tie(0);
  115.  
  116. 	int t; cin >> t;
  117. 	while (t--){
  118. 		int n; cin >> n;
  119.  
  120. 		read1(n);
  121.  
  122. 		for (int i = 0; i < mx + my; ++i){
  123. 			if (DG[i] & 1){
  124. 				S = stack<int>();
  125. 				dfs(i);
  126. 				make();
  127. 			}
  128. 		}
  129.  
  130. 		for (int i = 0; i < mx + my; ++i){
  131. 			if (DG[i]){
  132. 				S = stack<int>();
  133. 				dfs(i);
  134. 				make();
  135. 			}
  136. 		}
  137.  
  138. 		for (int i = 0; i < n; ++i) cout << ANS[i];
  139. 		cout << endl;
  140. 	}
  141.  
  142. 	return 0;
  143. }
  144.  
Success #stdin #stdout 0s 32536KB
comments (?)
stdin
copy 
1
10
2 4 8 2 5 6 9 5
stdout
copy 
AAAAABBBBB
https://ideone.com/WvvB6n
language:
C++ (gcc 8.3)
created:
9 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!