Submission #442327

#	Time	Username	Problem	Language	Result	Execution time	Memory
442327		minoum	Trobojnica (COCI19_trobojnica)	C++17	110 / 110	279 ms	19416 KiB

trobojnica

#include<bits/stdc++.h>

using namespace std;
typedef long long int ll;

const int MAXN = 2e5+10;

int n, cnt[4], nxt[MAXN], nxtc[MAXN], prv[MAXN], prvc[MAXN];
string s;
vector <pair<pair<int,int>,int>> ans;
set <int> dif[4];

inline int oth(int x, int y){
	if(x!=1&&y!=1) return 1;
	if(x!=2&&y!=2) return 2;
	return 3;
}

inline void add(int i){
	if(nxtc[i]!=prvc[i]){
		dif[nxtc[i]].insert(i);
		dif[prvc[i]].insert(i);
	}
	return;
}

inline void rmv(int i){
	if(nxtc[i]!=prvc[i]){
		dif[nxtc[i]].erase(i);
		dif[prvc[i]].erase(i);
	}
	return;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> s;
	for(int i = 0; i < n; i++) cnt[s[i]-'0']++;
	if((cnt[1]%2!=n%2)||(cnt[2]%2!=n%2)||(cnt[3]%2!=n%2)||(cnt[1]==n)||(cnt[2]==n)||(cnt[3]==n)){
		cout << "NE" << endl;
		return 0;
	}
	for(int i = 1; i <= n; i++) nxt[i] = (i%n)+1, nxtc[i] = s[i-1]-'0';
	for(int i = 1; i <= n; i++){
		prv[i] = (i==1?n:i-1), prvc[i] = nxtc[prv[i]]; 
		add(i);
	} 
	while((int)ans.size()<n-3){
		int mx;
		if(cnt[1]>=cnt[2]&&cnt[1]>=cnt[3]) mx = 1;
		else mx = ((cnt[2]>=cnt[1]&&cnt[2]>=cnt[3])?2:3);
		int ind = *dif[mx].begin();
		int cc = oth(nxtc[ind],prvc[ind]), nx = nxt[ind], pr = prv[ind];
	//	cout << "mx:" << mx << "  ind:" << ind << "  nx:"<< nx << "  pr:" << pr << "  nxc:" << nxtc[ind] << "  prc:" << prvc[ind] << "  cc:" << cc << endl;
		ans.push_back({{nxt[ind],prv[ind]},cc});
		cnt[cc]++; cnt[nxtc[ind]]--; cnt[prvc[ind]]--;
		rmv(ind); rmv(nx); rmv(pr);
		nxt[pr] = nx; prv[nx] = pr;
		nxtc[pr] = cc; prvc[nx] = cc;
		add(nx); add(pr);
	}
	cout << "DA" << endl;
	for(auto i: ans) cout << i.first.first << " " << i.first.second << " " << i.second << '\n';
	return 0; 
}

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50