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. void dfs(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. 		mk[cur.second] = true;
  52. 		DG[ X[cur.second] ]--;
  53. 		DG[ Y[cur.second] ]--;
  54. 		dfs(cur.first);
  55. 		break;
  56. 	}
  57. 	S.push(s);
  58. }
  59.  
  60. void make(){
  61. 	if (S.empty()) return;
  62. 	int a = S.top(); S.pop();
  63. //	cout << a << endl;
  64. 	int cur = 0;
  65. 	while (!S.empty()){
  66. 		int b = S.top(); S.pop();
  67. //		cout << b << endl;
  68. 		int u = a, v = b;
  69. 		if (v < u) swap(u, v);
  70.  
  71. //		assert(0 <= u && u < mx);
  72. //		assert(mx <= v && v < mx + my);
  73.  
  74. //		cout << u << " " << v << " " << M[ MP(u, v) ] << endl;
  75. 		ANS[M[MP(u,v)]] = 'A' + cur;
  76. 		++cnt;
  77. 		cur ^= 1;
  78. 		a = b;
  79. 	}
  80. //	cout << endl;
  81. }
  82.  
  83. void read1(int n){
  84. 	int x1, y1, ax, bx, ay, by;
  85. 	cin >> x1 >> y1 >> ax >> bx >> mx >> ay >> by >> my;
  86.  
  87. //	assert(1 <= n && n <= 100000);
  88. //	assert(1 <= mx && mx <= 100);
  89. //	assert(1 <= my && my <= 100);
  90.  
  91. 	init(mx + my);
  92.  
  93. 	for (int i = 0; i < n; ++i){
  94. 		add_edge(x1, mx + y1);
  95. //		cout << x1 << " " << y1 << endl;
  96. 		x1 = (1LL * ax * x1 + bx) % mx;
  97. 		y1 = (1LL * ay * y1 + by) % my;
  98. 	}
  99.  
  100. //	assert(edg == n);
  101. }
  102.  
  103. void read2(int n)
  104. {
  105. 	cin >> mx >> my;
  106. 	init(mx + my);
  107. 	for (int i = 0; i < n; ++i){
  108. 		int u, v;
  109. 		cin >> u >> v;
  110. //		cout << u << " " << v + mx << endl;
  111. 		add_edge(u, v + mx);
  112. 	}
  113. }
  114.  
  115. int main()
  116. {
  117. 	ios_base::sync_with_stdio(0);
  118. 	cin.tie(0);
  119.  
  120. 	int t; cin >> t;
  121. 	while (t--){
  122. 		int n; cin >> n;
  123.  
  124. 		read1(n);
  125.  
  126. 		for (int i = 0; i < mx + my; ++i){
  127. 			if (DG[i] & 1){
  128. 				S = stack<int>();
  129. 				dfs(i);
  130. 				make();
  131. 			}
  132. 		}
  133.  
  134. 		for (int i = 0; i < mx + my; ++i){
  135. 			if (DG[i]){
  136. 				S = stack<int>();
  137. 				dfs(i);
  138. 				make();
  139. 			}
  140. 		}
  141.  
  142. //		assert(cnt == n);
  143.  
  144. 		for (int i = 0; i < n; ++i) cout << ANS[i];
  145. 		cout << endl;
  146. 	}
  147.  
  148. 	return 0;
  149. }
Success #stdin #stdout 0s 32536KB
comments (?)
stdin
copy 
1
10
2 4 8 2 5 6 9 5
stdout
copy 
AAAAABBBBB
https://ideone.com/ENk8UO
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

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!