Submission #1266260

#TimeUsernameProblemLanguageResultExecution timeMemory
1266260keremTrobojnica (COCI19_trobojnica)C++20
110 / 110
36 ms12856 KiB
#include <bits/stdc++.h> using namespace std; //~ #define int int64_t #define pb push_back #define fr first #define sc second #define all(x) x.begin(),x.end() #define sp << " " << #define N 200000 typedef pair<int,int> pii; struct Item{ int color,next[2],p[2]; Item(int x,int c,int n){ color=c; p[0]=x;p[1]=(x+1)%n; next[0]=(x+n-1)%n; next[1]=(x+1)%n; } }; void solve(){ int n;string s; cin >> n >> s; vector<Item> a; int cnt[5]={0,0,0,0,0}; for(int i=0;i<n;i++){ cnt[s[i]-'0']++; a.pb(Item(i,s[i]-'0',n)); } if(cnt[1]%2!=cnt[2]%2 || cnt[2]%2!=cnt[3]%2 || max(cnt[1],max(cnt[2],cnt[3]))==cnt[1]+cnt[2]+cnt[3]){ cout << "NE\n"; return; } vector<tuple<int,int,int>> ans; int it=0,yon=1; while((int)ans.size()<n-3){ if(a[it].color==a[a[it].next[yon]].color){ int tmp=a[it].color; while(a[it].color==tmp) it=a[it].next[yon]; yon^=1; } int curColor=a[it].color,nextColor=a[a[it].next[yon]].color; if(cnt[curColor]==1 && cnt[nextColor]==1){ it=a[it].next[yon]; curColor=a[it].color; nextColor=a[a[it].next[yon]].color; } cnt[curColor]--;cnt[nextColor]--;cnt[6-curColor-nextColor]++; ans.pb({a[it].p[yon^1],a[a[it].next[yon]].p[yon],6-curColor-nextColor}); a[it].p[yon]=a[a[it].next[yon]].p[yon]; a[a[a[it].next[yon]].next[yon]].next[yon^1]=it; a[it].next[yon]=a[a[it].next[yon]].next[yon]; a[it].color=6-curColor-nextColor; } cout << "DA\n"; for(auto [i,j,c]:ans) cout << i+1 sp j+1 sp c << "\n"; } int32_t main(){ //~ freopen("radio.in","r",stdin); //~ freopen("radio.out","w",stdout); cout << fixed << setprecision(0); ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); int test=1; //~ cin >> test; while(test--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...