fork download
copy 
  1. #include <bits/stdc++.h>
  2. // iostream is too mainstream
  3. #include <cstdio>
  4. // bitch please
  5. #include <iostream>
  6. #include <algorithm>
  7. #include <cstdlib>
  8. #include <vector>
  9. #include <set>
  10. #include <map>
  11. #include <queue>
  12. #include <stack>
  13. #include <list>
  14. #include <cmath>
  15. #include <iomanip>
  16. #include <time.h>
  17. #define dibs reserve
  18. #define OVER9000 1234567890
  19. #define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
  20. #define tisic 47
  21. #define soclose 1e-8
  22. #define chocolate win
  23. // so much chocolate
  24. #define patkan 9
  25. #define ff first
  26. #define ss second
  27. #define abs(x) (((x) < 0)?-(x):(x))
  28. #define uint unsigned int
  29. #define dbl long double
  30. #define pi 3.14159265358979323846
  31. using namespace std;
  32. // mylittledoge
  33.  
  34. using cat = long long;
  35.  
  36. #ifdef DONLINE_JUDGE
  37. 	// palindromic tree is better than splay tree!
  38. 	#define lld I64d
  39. #endif
  40.  
  41. struct seg {
  42. 	int l, r, id;
  43.  
  44. 	bool operator<(const seg & S) const {
  45. 		if(l != S.l) return l < S.l;
  46. 		return r < S.r;
  47. 	}
  48. };
  49.  
  50. int main() {
  51. 	cin.sync_with_stdio(0);
  52. 	cin.tie(0);
  53. 	cout << fixed << setprecision(10);
  54. 	int L, N;
  55. 	cin >> L >> N;
  56. 	vector<seg> A(N);
  57. 	int max_dif = 0, max_dif_id = -1;
  58. 	for(int i = 0; i < N; i++) {
  59. 		cin >> A[i].l >> A[i].r;
  60. 		A[i].l--, A[i].r--;
  61. 		A[i].id = i;
  62. 		int dif = (A[i].r >= A[i].l) ? (A[i].r-A[i].l+1) : (A[i].r+1+L-A[i].l);
  63. 		if(dif > max_dif) {
  64. 			max_dif = dif;
  65. 			max_dif_id = i;
  66. 		}
  67. 	}
  68. 	sort(begin(A), end(A));
  69. 	for(int i = 0; i < N; i++) if(max_dif_id == A[i].id) {
  70. 		max_dif_id = i;
  71. 		break;
  72. 	}
  73. 	set< pair<int, int> > open;
  74. 	for(int i = 0; i < N; i++) if(A[i].l == 0 || A[i].r < A[i].l)
  75. 		open.insert({A[i].r+1, i});
  76. 	int a = 0;
  77. 	while(a < N && A[a].l == 0) a++;
  78. 	vector< set<int> > dif_col(N);
  79. 	int curx = 0;
  80. 	while(true) {
  81. 		if((int)open.size() <= 1) {
  82. 			cout << "impossible\n";
  83. 			return 0;
  84. 		}
  85. 		if(open.size() == 2) {
  86. 			dif_col[begin(open)->ss].insert(open.rbegin()->ss);
  87. 			dif_col[open.rbegin()->ss].insert(begin(open)->ss);
  88. 		}
  89. 		int x = L;
  90. 		auto it = open.upper_bound({curx, N+1});
  91. 		if(it != end(open)) x = it->ff;
  92. 		if(a < N) x = min(x, A[a].l);
  93. 		if(x == L) break;
  94. 		while(it != end(open) && it->ff == x) {
  95. 			auto jt = it;
  96. 			it++;
  97. 			open.erase(jt);
  98. 		}
  99. 		while(a < N && A[a].l == x) {
  100. 			open.insert({A[a].r+1, a});
  101. 			a++;
  102. 		}
  103. 		curx = x;
  104. 	}
  105. 	map<int, vector<int> > starts;
  106. 	for(int i = 0; i < N; i++) starts[A[i].l].push_back(i);
  107. 	int cur = max_dif_id;
  108. 	set<int> bl;
  109. 	queue< pair<int, int> > q;
  110. 	q.push({cur, 1});
  111. 	vector<bool> vis(N, false);
  112. 	vis[cur] = true;
  113. 	while(!q.empty()) {
  114. 		ALL_THE(dif_col[q.front().ff], it) if(!vis[*it]) {
  115. 			if(q.front().ss == 1) bl.insert(*it);
  116. 			vis[*it] = true;
  117. 			q.push({*it, 1-q.front().ss});
  118. 		}
  119. 		q.pop();
  120. 	}
  121. 	ALL_THE(bl, it) ALL_THE(dif_col[*it], jt) if(bl.find(*jt) != bl.end()) {
  122. 		cout << "impossible\n";
  123. 		return 0;
  124. 	}
  125. 	vector<bool> ans(N, 0);
  126. 	ans[cur] = 1;
  127. 	int l = A[cur].l, r = (A[cur].r+1)%L;
  128. 	int cov = A[cur].r+1-A[cur].l;
  129. 	if(cov <= 0) cov += L;
  130. 	while(cov < L) {
  131. 		ALL_THE(dif_col[cur], it) bl.insert(*it);
  132. 		bl.insert(cur);
  133. 		int r_nxt = -1, id_nxt = -1;
  134. 		for(int i = l; ; i = (i+1)%L) {
  135. 			if(starts.empty()) break;
  136. 			auto it = starts.lower_bound(i);
  137. 			if(it == end(starts)) it = begin(starts);
  138. 			int cp = it->ff, rp = r;
  139. 			if(cp < l) cp += L;
  140. 			if(rp < l) rp += L;
  141. 			if(cp > rp) break;
  142. 			i = it->ff;
  143. 			ALL_THE(it->ss, jt) {
  144. 				if(bl.find(*jt) != end(bl)) continue;
  145. 				// ignore segments that don't extend cover(1)
  146. 				if(A[cur].r >= A[cur].l) {
  147. 					if(A[*jt].r <= A[cur].r && A[*jt].l >= A[cur].l && A[*jt].l <= A[*jt].r) continue; 
  148. 				}
  149. 				else {
  150. 					if(A[*jt].r <= A[cur].r && A[*jt].l >= A[cur].l) continue;
  151. 					if(A[*jt].r <= A[cur].r && A[*jt].l <= A[*jt].r) continue;
  152. 					if(A[*jt].l >= A[cur].l && A[*jt].l <= A[*jt].r) continue;
  153. 				}
  154. 				int x = A[*jt].r+1;
  155. 				if(x <= l) x += L;
  156. 				if(x > r_nxt) {
  157. 					r_nxt = x;
  158. 					id_nxt = *jt;
  159. 				}
  160. 			}
  161. 			starts.erase(it);
  162. 		}
  163. 		assert(id_nxt != -1);
  164. 		int r_old = r;
  165. 		if(r_old < l) r_old += L;
  166. 		assert(r_nxt != r_old);
  167. 		cov += (r_nxt-r_old+10*L)%L;
  168. 		l = r;
  169. 		r = (A[id_nxt].r+1)%L;
  170. 		ans[id_nxt] = 1;
  171. 		cur = id_nxt;
  172. 	}
  173. 	vector<int> ans_orig(N);
  174. 	for(int i = 0; i < N; i++) ans_orig[A[i].id] = ans[i];
  175. 	for(int i = 0; i < N; i++) cout << (int) ans_orig[i];
  176. 	cout << "\n";
  177. 	return 0;
  178. }
  179.  
  180. // look at my code
  181. // my code is amazing
  182.  
Success #stdin #stdout 0s 4284KB
comments (?)
stdin
copy 
13 17

1 10
3 11
12 3
1 1
2 2
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 12
12 12
13 13
13 13
stdout
copy 
11100000000000000
https://ideone.com/vjAn4v
BOI 2018 day 2 A: Alternating Current
incorrect solution, gets AC
language:
C++14 (gcc 8.3)
created:
5 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!