#include <bits/stdc++.h>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define befv(V) ((V)[(sz(V)-2)])
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
void fuk() { puts("impossible"); exit(0); }
const bool debug = 0;
const int MAXN = 100005;
const int MAXM = 100005;
struct PFS {
int d[MAXN*2], N;
void init() { fill(d, d+MAXN*2, 0); }
void add(int s, int e) { d[s]++; d[e+1]--; }
bool cal() {
for(int i = 1; i <= N*2; i++) d[i+1] += d[i];
for(int i = 1; i <= N; i++)
if(!d[i] && !d[i+N]) return false;
return true;
}
} preA, preB;
vector<int> T[MAXN*2];
vector<int> G[MAXM], CH;
int ud[MAXM];
int A[MAXM], B[MAXM];
int Ans[MAXM];
int N, M;
int uf(int i) { return i == ud[i] ? i : (ud[i] = uf(ud[i])); }
void uf(int a, int b) { ud[uf(b)] = uf(a); }
bool isValid() {
preA.init(); preB.init();
for(int i = 1; i <= M; i++)
(Ans[i] ? preA : preB).add(A[i], B[i]);
return preA.cal() && preB.cal();
}
int main() {
ios::sync_with_stdio(false);
cin >> N >> M;
preA.N = preB.N = N;
for(int i = 1; i <= M; i++) {
cin >> A[i] >> B[i];
if(A[i] > B[i]) B[i] += N;
if(B[i]-A[i] == N-1) { A[i] = 1; B[i] = N; }
T[A[i]].eb(i);
T[A[i]+N].eb(i);
if(debug) printf("%d ; %d %d\n", i, A[i], B[i]);
}
iota(ud, ud+MAXM, 0);
{
int ci = -1;
for(int i = 1; i <= M; i++)
if(1 == A[i] && B[i] == N)
ci = i;
if(0 < ci) {
for(int i = 1; i <= M; i++)
uf(ci, i);
} else {
for(int i = 1; i <= M; i++) for(int j = 1; j <= M; j++) {
if(A[i] <= A[j] && B[j] <= B[i]) uf(i, j);
else if(A[i]+N <= A[j] && B[j] <= B[i]+N) uf(i, j);
else if(A[i] <= A[j]+N && B[j]+N <= B[i]) uf(i, j);
}
/*
for(int i = 1, st = 0, et = 0, ei = -1; i <= N*2; i++) {
for(int v : T[i]) {
int e = i + (B[v]-A[v]);
if(e <= et) uf(ei, v);
else {
if(st == i) uf(v, ei);
st = i; et = e; ei = v;
}
}
}
*/
}
}
for(int i = 1; i <= M; i++) (uf(i) == i ? CH : G[uf(i)]).eb(i);
sort(allv(CH), [&](int a, int b) { return A[a] < A[b]; });
if(debug) {
for(int i = 1; i <= M; i++) printf("%d ; %d\n", i, uf(i));
for(int v : CH) printf("%d ", v); puts("");
}
/*
for(int v : CH) preA.add(A[v], B[v]);
if(!preA.cal()) fuk();
preA.init();
*/
if(sz(CH) & 1) {
for(int i = 0, n = sz(CH); i < n; i++) {
for(int j = 0; j < i; j++) Ans[CH[j]] = (i-j-1) & 1;
for(int j = i; j < n; j++) Ans[CH[j]] = (j-i) & 1;
for(int j = 1; j <= M; j++) if(uf(j) != j)
Ans[j] = !Ans[uf(j)];
if(isValid()) break;
}
} else {
for(int i = 0, n = sz(CH); i < n; i++)
Ans[CH[i]] = i & 1;
for(int i = 1; i <= M; i++) if(uf(i) != i)
Ans[i] = !Ans[uf(i)];
}
if(!isValid()) fuk();
for(int i = 1; i <= M; i++) printf("%d", !!Ans[i]);
puts("");
return 0;
}
Compilation message
alternating.cpp: In function 'int main()':
alternating.cpp:107:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for(int v : CH) printf("%d ", v); puts("");
^~~
alternating.cpp:107:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for(int v : CH) printf("%d ", v); puts("");
^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
9300 KB |
Output is correct |
| 2 |
Correct |
12 ms |
9448 KB |
Output is correct |
| 3 |
Correct |
13 ms |
9528 KB |
Output is correct |
| 4 |
Correct |
11 ms |
9528 KB |
Output is correct |
| 5 |
Correct |
12 ms |
9528 KB |
Output is correct |
| 6 |
Incorrect |
11 ms |
9528 KB |
'impossible' claimed, but there is a solution |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
9300 KB |
Output is correct |
| 2 |
Correct |
12 ms |
9448 KB |
Output is correct |
| 3 |
Correct |
13 ms |
9528 KB |
Output is correct |
| 4 |
Correct |
11 ms |
9528 KB |
Output is correct |
| 5 |
Correct |
12 ms |
9528 KB |
Output is correct |
| 6 |
Incorrect |
11 ms |
9528 KB |
'impossible' claimed, but there is a solution |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
9300 KB |
Output is correct |
| 2 |
Correct |
12 ms |
9448 KB |
Output is correct |
| 3 |
Correct |
13 ms |
9528 KB |
Output is correct |
| 4 |
Correct |
11 ms |
9528 KB |
Output is correct |
| 5 |
Correct |
12 ms |
9528 KB |
Output is correct |
| 6 |
Incorrect |
11 ms |
9528 KB |
'impossible' claimed, but there is a solution |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
47 ms |
12068 KB |
Output is correct |
| 2 |
Correct |
14 ms |
12068 KB |
Output is correct |
| 3 |
Correct |
40 ms |
13592 KB |
Output is correct |
| 4 |
Correct |
53 ms |
13712 KB |
Output is correct |
| 5 |
Execution timed out |
3024 ms |
13712 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
9300 KB |
Output is correct |
| 2 |
Correct |
12 ms |
9448 KB |
Output is correct |
| 3 |
Correct |
13 ms |
9528 KB |
Output is correct |
| 4 |
Correct |
11 ms |
9528 KB |
Output is correct |
| 5 |
Correct |
12 ms |
9528 KB |
Output is correct |
| 6 |
Incorrect |
11 ms |
9528 KB |
'impossible' claimed, but there is a solution |
| 7 |
Halted |
0 ms |
0 KB |
- |
