# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
251466 | 2020-07-21T10:20:49 Z | Bruteforceman | Trobojnica (COCI19_trobojnica) | C++11 | 197 ms | 16248 KB |
#include <bits/stdc++.h> using namespace std; const int maxn = 2e5 + 10; #define endl '\n' int suc[maxn]; int pre[maxn]; int succol[maxn], precol[maxn]; char a[maxn]; int main() { int n; scanf("%d", &n); scanf("%s", a); int freq[] = {0, 0, 0, 0}; set <int> s[4][4]; for(int i = 0; i < n; i++) { pre[i] = (n + i - 1) % n; suc[i] = (i + 1) % n; freq[a[i] - '0'] += 1; precol[i] = a[pre[i]] - '0'; succol[i] = a[i] - '0'; s[precol[i]][succol[i]].insert(i); } if(freq[1] == n || freq[2] == n || freq[3] == n) { puts("NE"); exit(0); } if(abs(freq[1] - freq[2]) % 2 == 1 || abs(freq[2] - freq[3]) % 2 == 1) { puts("NE"); exit(0); } puts("DA"); int cur = 0; for(int i = 0; i < n - 3; i++) { int occur = max({freq[1], freq[2], freq[3]}); int col; for(col = 1; col <= 3; col++) { if(freq[col] == occur) break; } bool done = false; for(int x = 1; x <= 3; x++) { for(int y = 1; y <= 3; y++) { if(s[x][y].empty()) continue; if(x == y || (x != col && y != col)) continue; if(done) continue; int cur = *s[x][y].begin(); s[x][y].erase(cur); int p = pre[cur]; int q = suc[cur]; int inv = 6 - x - y; freq[x] -= 1; freq[y] -= 1; freq[inv] += 1; printf("%d %d %d\n", p + 1, q + 1, inv); s[precol[p]][succol[p]].erase(p); s[precol[q]][succol[q]].erase(q); pre[suc[cur]] = pre[cur]; precol[suc[cur]] = inv; suc[pre[cur]] = suc[cur]; succol[pre[cur]] = inv; s[precol[p]][succol[p]].insert(p); s[precol[q]][succol[q]].insert(q); done = true; } } } return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 0 ms | 384 KB | Output is correct |
3 | Correct | 0 ms | 384 KB | Output is correct |
4 | Correct | 0 ms | 384 KB | Output is correct |
5 | Correct | 1 ms | 384 KB | Output is correct |
6 | Correct | 0 ms | 384 KB | Output is correct |
7 | Correct | 0 ms | 384 KB | Output is correct |
8 | Correct | 0 ms | 384 KB | Output is correct |
9 | Correct | 0 ms | 384 KB | Output is correct |
10 | Correct | 0 ms | 384 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 0 ms | 384 KB | Output is correct |
3 | Correct | 0 ms | 384 KB | Output is correct |
4 | Correct | 0 ms | 384 KB | Output is correct |
5 | Correct | 1 ms | 384 KB | Output is correct |
6 | Correct | 0 ms | 384 KB | Output is correct |
7 | Correct | 0 ms | 384 KB | Output is correct |
8 | Correct | 0 ms | 384 KB | Output is correct |
9 | Correct | 0 ms | 384 KB | Output is correct |
10 | Correct | 0 ms | 384 KB | Output is correct |
11 | Correct | 0 ms | 384 KB | Output is correct |
12 | Correct | 1 ms | 384 KB | Output is correct |
13 | Correct | 1 ms | 384 KB | Output is correct |
14 | Correct | 0 ms | 384 KB | Output is correct |
15 | Correct | 0 ms | 384 KB | Output is correct |
16 | Correct | 1 ms | 384 KB | Output is correct |
17 | Correct | 1 ms | 384 KB | Output is correct |
18 | Correct | 2 ms | 384 KB | Output is correct |
19 | Correct | 1 ms | 384 KB | Output is correct |
20 | Correct | 2 ms | 384 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 0 ms | 384 KB | Output is correct |
3 | Correct | 0 ms | 384 KB | Output is correct |
4 | Correct | 0 ms | 384 KB | Output is correct |
5 | Correct | 1 ms | 384 KB | Output is correct |
6 | Correct | 0 ms | 384 KB | Output is correct |
7 | Correct | 0 ms | 384 KB | Output is correct |
8 | Correct | 0 ms | 384 KB | Output is correct |
9 | Correct | 0 ms | 384 KB | Output is correct |
10 | Correct | 0 ms | 384 KB | Output is correct |
11 | Correct | 0 ms | 384 KB | Output is correct |
12 | Correct | 1 ms | 384 KB | Output is correct |
13 | Correct | 1 ms | 384 KB | Output is correct |
14 | Correct | 0 ms | 384 KB | Output is correct |
15 | Correct | 0 ms | 384 KB | Output is correct |
16 | Correct | 1 ms | 384 KB | Output is correct |
17 | Correct | 1 ms | 384 KB | Output is correct |
18 | Correct | 2 ms | 384 KB | Output is correct |
19 | Correct | 1 ms | 384 KB | Output is correct |
20 | Correct | 2 ms | 384 KB | Output is correct |
21 | Correct | 150 ms | 16248 KB | Output is correct |
22 | Correct | 171 ms | 15356 KB | Output is correct |
23 | Correct | 1 ms | 384 KB | Output is correct |
24 | Correct | 0 ms | 384 KB | Output is correct |
25 | Correct | 197 ms | 16168 KB | Output is correct |
26 | Correct | 1 ms | 384 KB | Output is correct |
27 | Correct | 93 ms | 8184 KB | Output is correct |
28 | Correct | 32 ms | 13180 KB | Output is correct |
29 | Correct | 0 ms | 384 KB | Output is correct |
30 | Correct | 43 ms | 13304 KB | Output is correct |