//!yrt tsuj uoy srettam gnihton no emoc
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define pii pair <int, int>
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define F first
#define S second
const int maxn = 5e5 + 5;
struct edge{
int c, l, r, u, v;
} ed[maxn];
int t[5];
vector <int> vec[maxn];
bool mark[maxn];
int cnt;
int find_mx(){
pii v[] = {{t[0], 0}, {t[1], 1}, {t[2], 2}};
sort(v, v + 3);
return v[2].S;
}
void upd(int le, int x){
ed[cnt].c = 2 * (ed[x].c + ed[le].c) % 3;
ed[cnt].l = ed[le].l;
ed[cnt].r = ed[x].r;
ed[cnt].u = ed[le].u;
ed[cnt].v = ed[x].v;
cout << ed[cnt].u + 1 << " " << ed[cnt].v + 1 << " " << ed[cnt].c + 1 << endl;
mark[x] = mark[le] = true;
vec[ed[cnt].c].pb(cnt);
vec[ed[ed[cnt].l].c].pb(ed[cnt].l);
vec[ed[ed[cnt].r].c].pb(ed[cnt].r);
t[ed[cnt].c] ++;
t[ed[le].c] --;
t[ed[x].c] --;
cnt ++;
return;
}
bool check(int x){
if(mark[x]){
return false;
}
int le = ed[x].l;
int ri = ed[x].r;
if(ed[x].c != ed[le].c && !mark[le]){
upd(le, x);
return true;
}
if(ed[x].c != ed[ri].c && !mark[ri]){
upd(x, ri);
return true;
}
return false;
}
void solve(int n){
if(n == 3){
return;
}
int mx = find_mx();
bool f = true;
while(f){
int x = vec[mx].back();
vec[mx].pop_back();
if(check(x)){
f = false;
}
}
solve(n - 1);
}
int main(){
fast_io;
int n;
cin >> n;
string s; cin >> s;
for(int i = 0; i < n; i ++){
ed[i].c = (s[i] - '0') - 1;
ed[i].u = i;
ed[i].v = (i + 1) % n;
ed[i].l = (i - 1 + n) % n;
ed[i].r = (i + 1) % n;
t[ed[i].c] ++;
vec[ed[i].c].pb(i);
}
for(int i = 0; i < 3; i ++){
if((t[i] & 1) != (n & 1) || t[i] == n){
cout << "NE";
return 0;
}
}
cnt = n;
cout << "DA" << endl;
solve(n);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
11980 KB |
Output is correct |
| 2 |
Correct |
8 ms |
11980 KB |
Output is correct |
| 3 |
Runtime error |
22 ms |
24268 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
11980 KB |
Output is correct |
| 2 |
Correct |
8 ms |
11980 KB |
Output is correct |
| 3 |
Runtime error |
22 ms |
24268 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
11980 KB |
Output is correct |
| 2 |
Correct |
8 ms |
11980 KB |
Output is correct |
| 3 |
Runtime error |
22 ms |
24268 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
