Submission #439310

#TimeUsernameProblemLanguageResultExecution timeMemory
439310negar_aTrobojnica (COCI19_trobojnica)C++14
0 / 110
4 ms4940 KiB
//!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 = 2e5 + 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; } 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){ 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 true; } if(ed[x].c != ed[ri].c){ ed[cnt].c = 2 * (ed[x].c + ed[ri].c) % 3; ed[cnt].l = ed[x].l; ed[cnt].r = ed[ri].r; ed[cnt].u = ed[x].u; ed[cnt].v = ed[ri].v; cout << ed[cnt].u + 1 << " " << ed[cnt].v + 1 << " " << ed[cnt].c << endl; mark[x] = mark[ri] = true; t[ed[cnt].c] ++; t[ed[ri].c] --; t[ed[x].c] --; 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); cnt ++; 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){ assert(0); cout << "NE"; return 0; } } cnt = n; cout << "DA" << endl; solve(n); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...