| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 63219 | 2018-08-01T06:23:43 Z | 김세빈(#1833) | Alternating Current (BOI18_alternating) | C++11 | 177 ms | 18808 KB |
#include <bits/stdc++.h>
using namespace std;
typedef pair <int, int> pii;
vector <int> L[101010], V[101010];
vector <int> X[101010], Y[101010];
set <int> S;
pii P[101010];
int chk[101010], ans[101010];
int fff[101010];
int n, m;
void die() { printf("impossible\n"); exit(0); }
void dfs(int p, int c)
{
chk[p] = 2; ans[p] = c;
for(int &t: V[p]){
if(chk[t] == 1) dfs(t, !c);
else if(ans[t] == ans[p]) die();
}
}
int main()
{
int i, s, e, x, y, a, b;
scanf("%d%d", &n, &m);
for(i=1; i<=m; i++){
scanf("%d%d", &a, &b);
b ++; if(b > n) b -= n;
P[i] = pii(a, b);
if(a < b){
L[a].push_back(i);
L[b].push_back(-i);
}
else{
L[1].push_back(i);
L[b].push_back(-i);
L[a].push_back(i);
}
}
for(i=1; i<=n; i++){
for(int &t: L[i]){
if(t > 0) S.insert(t);
else S.erase(-t);
}
if(S.size() == 2){
a = *S.begin(); b = *next(S.begin());
V[a].push_back(b);
V[b].push_back(a);
chk[a] = 1; chk[b] = 1;
}
else if(S.size() == 1) die();
}
for(i=1; i<=m; i++){
if(chk[i] == 1) dfs(i, 0);
}
x = 1;
for(i=1; i<=m; i++){
if(chk[i]){
if(ans[i] == 1) x = i;
}
}
ans[x] = 1;
s = P[x].first;
for(i=1; i<=m; i++){
P[i].first = (P[i].first - s + n) % n + 1;
P[i].second = (P[i].second - s + n) % n + 1;
if(P[i].first >= P[i].second) P[i].second += n;
if(chk[i] && ans[i] == 1) X[P[i].first].push_back(i);
else if(!chk[i]) Y[P[i].first].push_back(i);
}
e = P[x].second; y = -1;
for(i=1; i<=n+1; i++){
for(int &t: X[i]) e = max(e, P[t].second);
for(int &t: Y[i]){
if(y == -1) y = t;
else if(P[t].second > P[y].second) y = t;
}
if(i == e){
ans[y] = 1;
e = P[y].second;
y = -1;
}
}
for(i=1; i<=m; i++) printf("%d", ans[i]);
printf("\n");
return 0;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 10 ms | 9720 KB | Output is correct |
| 2 | Correct | 10 ms | 9832 KB | Output is correct |
| 3 | Correct | 12 ms | 10032 KB | Output is correct |
| 4 | Correct | 11 ms | 10032 KB | Output is correct |
| 5 | Correct | 10 ms | 10032 KB | Output is correct |
| 6 | Correct | 10 ms | 10032 KB | Output is correct |
| 7 | Correct | 10 ms | 10060 KB | Output is correct |
| 8 | Correct | 12 ms | 10084 KB | Output is correct |
| 9 | Correct | 12 ms | 10216 KB | Output is correct |
| 10 | Correct | 11 ms | 10216 KB | Output is correct |
| 11 | Correct | 12 ms | 10216 KB | Output is correct |
| 12 | Correct | 12 ms | 10216 KB | Output is correct |
| 13 | Correct | 12 ms | 10216 KB | Output is correct |
| 14 | Correct | 11 ms | 10216 KB | Output is correct |
| 15 | Correct | 9 ms | 10216 KB | Output is correct |
| 16 | Correct | 10 ms | 10216 KB | Output is correct |
| 17 | Correct | 10 ms | 10216 KB | Output is correct |
| 18 | Correct | 10 ms | 10216 KB | Output is correct |
| 19 | Correct | 9 ms | 10216 KB | Output is correct |
| 20 | Correct | 13 ms | 10236 KB | Output is correct |
| 21 | Correct | 11 ms | 10240 KB | Output is correct |
| 22 | Correct | 10 ms | 10240 KB | Output is correct |
| 23 | Correct | 14 ms | 10240 KB | Output is correct |
| 24 | Correct | 10 ms | 10240 KB | Output is correct |
| 25 | Correct | 10 ms | 10240 KB | Output is correct |
| 26 | Correct | 11 ms | 10240 KB | Output is correct |
| 27 | Incorrect | 12 ms | 10240 KB | no wires in direction 0 between segments 15 and 15 |
| 28 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 10 ms | 9720 KB | Output is correct |
| 2 | Correct | 10 ms | 9832 KB | Output is correct |
| 3 | Correct | 12 ms | 10032 KB | Output is correct |
| 4 | Correct | 11 ms | 10032 KB | Output is correct |
| 5 | Correct | 10 ms | 10032 KB | Output is correct |
| 6 | Correct | 10 ms | 10032 KB | Output is correct |
| 7 | Correct | 10 ms | 10060 KB | Output is correct |
| 8 | Correct | 12 ms | 10084 KB | Output is correct |
| 9 | Correct | 12 ms | 10216 KB | Output is correct |
| 10 | Correct | 11 ms | 10216 KB | Output is correct |
| 11 | Correct | 12 ms | 10216 KB | Output is correct |
| 12 | Correct | 12 ms | 10216 KB | Output is correct |
| 13 | Correct | 12 ms | 10216 KB | Output is correct |
| 14 | Correct | 11 ms | 10216 KB | Output is correct |
| 15 | Correct | 9 ms | 10216 KB | Output is correct |
| 16 | Correct | 10 ms | 10216 KB | Output is correct |
| 17 | Correct | 10 ms | 10216 KB | Output is correct |
| 18 | Correct | 10 ms | 10216 KB | Output is correct |
| 19 | Correct | 9 ms | 10216 KB | Output is correct |
| 20 | Correct | 13 ms | 10236 KB | Output is correct |
| 21 | Correct | 11 ms | 10240 KB | Output is correct |
| 22 | Correct | 10 ms | 10240 KB | Output is correct |
| 23 | Correct | 14 ms | 10240 KB | Output is correct |
| 24 | Correct | 10 ms | 10240 KB | Output is correct |
| 25 | Correct | 10 ms | 10240 KB | Output is correct |
| 26 | Correct | 11 ms | 10240 KB | Output is correct |
| 27 | Incorrect | 12 ms | 10240 KB | no wires in direction 0 between segments 15 and 15 |
| 28 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 10 ms | 9720 KB | Output is correct |
| 2 | Correct | 10 ms | 9832 KB | Output is correct |
| 3 | Correct | 12 ms | 10032 KB | Output is correct |
| 4 | Correct | 11 ms | 10032 KB | Output is correct |
| 5 | Correct | 10 ms | 10032 KB | Output is correct |
| 6 | Correct | 10 ms | 10032 KB | Output is correct |
| 7 | Correct | 10 ms | 10060 KB | Output is correct |
| 8 | Correct | 12 ms | 10084 KB | Output is correct |
| 9 | Correct | 12 ms | 10216 KB | Output is correct |
| 10 | Correct | 11 ms | 10216 KB | Output is correct |
| 11 | Correct | 12 ms | 10216 KB | Output is correct |
| 12 | Correct | 12 ms | 10216 KB | Output is correct |
| 13 | Correct | 12 ms | 10216 KB | Output is correct |
| 14 | Correct | 11 ms | 10216 KB | Output is correct |
| 15 | Correct | 9 ms | 10216 KB | Output is correct |
| 16 | Correct | 10 ms | 10216 KB | Output is correct |
| 17 | Correct | 10 ms | 10216 KB | Output is correct |
| 18 | Correct | 10 ms | 10216 KB | Output is correct |
| 19 | Correct | 9 ms | 10216 KB | Output is correct |
| 20 | Correct | 13 ms | 10236 KB | Output is correct |
| 21 | Correct | 11 ms | 10240 KB | Output is correct |
| 22 | Correct | 10 ms | 10240 KB | Output is correct |
| 23 | Correct | 14 ms | 10240 KB | Output is correct |
| 24 | Correct | 10 ms | 10240 KB | Output is correct |
| 25 | Correct | 10 ms | 10240 KB | Output is correct |
| 26 | Correct | 11 ms | 10240 KB | Output is correct |
| 27 | Incorrect | 12 ms | 10240 KB | no wires in direction 0 between segments 15 and 15 |
| 28 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 125 ms | 17768 KB | Output is correct |
| 2 | Correct | 15 ms | 17768 KB | Output is correct |
| 3 | Correct | 39 ms | 17768 KB | Output is correct |
| 4 | Correct | 62 ms | 17768 KB | Output is correct |
| 5 | Correct | 177 ms | 18444 KB | Output is correct |
| 6 | Correct | 106 ms | 18444 KB | Output is correct |
| 7 | Correct | 160 ms | 18444 KB | Output is correct |
| 8 | Correct | 23 ms | 18444 KB | Output is correct |
| 9 | Correct | 16 ms | 18444 KB | Output is correct |
| 10 | Correct | 175 ms | 18808 KB | Output is correct |
| 11 | Correct | 143 ms | 18808 KB | Output is correct |
| 12 | Correct | 150 ms | 18808 KB | Output is correct |
| 13 | Incorrect | 15 ms | 18808 KB | no wires in direction 0 between segments 100000 and 100000 |
| 14 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 10 ms | 9720 KB | Output is correct |
| 2 | Correct | 10 ms | 9832 KB | Output is correct |
| 3 | Correct | 12 ms | 10032 KB | Output is correct |
| 4 | Correct | 11 ms | 10032 KB | Output is correct |
| 5 | Correct | 10 ms | 10032 KB | Output is correct |
| 6 | Correct | 10 ms | 10032 KB | Output is correct |
| 7 | Correct | 10 ms | 10060 KB | Output is correct |
| 8 | Correct | 12 ms | 10084 KB | Output is correct |
| 9 | Correct | 12 ms | 10216 KB | Output is correct |
| 10 | Correct | 11 ms | 10216 KB | Output is correct |
| 11 | Correct | 12 ms | 10216 KB | Output is correct |
| 12 | Correct | 12 ms | 10216 KB | Output is correct |
| 13 | Correct | 12 ms | 10216 KB | Output is correct |
| 14 | Correct | 11 ms | 10216 KB | Output is correct |
| 15 | Correct | 9 ms | 10216 KB | Output is correct |
| 16 | Correct | 10 ms | 10216 KB | Output is correct |
| 17 | Correct | 10 ms | 10216 KB | Output is correct |
| 18 | Correct | 10 ms | 10216 KB | Output is correct |
| 19 | Correct | 9 ms | 10216 KB | Output is correct |
| 20 | Correct | 13 ms | 10236 KB | Output is correct |
| 21 | Correct | 11 ms | 10240 KB | Output is correct |
| 22 | Correct | 10 ms | 10240 KB | Output is correct |
| 23 | Correct | 14 ms | 10240 KB | Output is correct |
| 24 | Correct | 10 ms | 10240 KB | Output is correct |
| 25 | Correct | 10 ms | 10240 KB | Output is correct |
| 26 | Correct | 11 ms | 10240 KB | Output is correct |
| 27 | Incorrect | 12 ms | 10240 KB | no wires in direction 0 between segments 15 and 15 |
| 28 | Halted | 0 ms | 0 KB | - |