Submission #229219

#	Time	Username	Problem	Language	Result	Execution time	Memory
229219		VEGAnn	Trobojnica (COCI19_trobojnica)	C++14	110 / 110	328 ms	43800 KiB

trobojnica

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define MP make_pair
#define PB push_back
#define ft first
#define sd second
#define pii pair<int, int>
#define pi3 pair<pii, int>
#define MP3(a, b,c) MP(MP(a, b), c)
#define sz(x) ((ll)x.size())
using namespace std;
typedef long long ll;
const ll N = 200100;
const ll oo = 1e18;
vector<pi3> vc;
unordered_map<int, int> col[N];
set<pi3> st[3][3];
int nx[N], pre[N], kol[N], n, obr[3];

void BAD(){
	cout << "NE";
	exit(0);
}

int MEX(int x, int y){
	if (x != 0 && y != 0) return 0;
	if (x != 1 && y != 1) return 1;
	return 2;
}

int main(){
	
	ios_base::sync_with_stdio(0); cin.tie(0);
	
//	freopen("in.txt","r",stdin);

	cin >> n;
	
	for (int i = 0; i < n; i++){
		char x; cin >> x;
		col[i][(i + 1) % n] = x - '1';
		kol[x - '1']++;
		nx[i] = (i + 1) % n;
		pre[i] = (i - 1 + n) % n;
	}
	
	for (int i = 1; i < n; i++) {
		int nt = (i + 1) % n;
		int nnt = (nt + 1) % n;
		st[col[i][nt]][col[nt][nnt]].insert(MP3(i, nt, nnt));
	}
	
	for (int it = n - 3; it >= 0; it--){
		if (it == 0){
			if (sz(st[1][1]) || sz(st[2][2]) || sz(st[0][0]))
				BAD();
		} else {
			bool was = 0;
			
			obr[0] = 0;
			obr[1] = 1;
			obr[2] = 2;
			
			if (kol[obr[0]]< kol[obr[1]]) swap(obr[0], obr[1]);
			if (kol[obr[1]]< kol[obr[2]]) swap(obr[1], obr[2]);
			if (kol[obr[0]]< kol[obr[1]]) swap(obr[0], obr[1]);
			
			for (int C1 = 0; C1 < 3 && !was; C1++)
			for (int C2 = 0; C2 < 3 && !was; C2++) {
				int c1 = obr[C1];
				int c2 = obr[C2];
				if (c1 != c2 && sz(st[c1][c2])){
					pi3 CR = (*st[c1][c2].begin());
					st[c1][c2].erase(st[c1][c2].begin());
					was = 1;
					
					int i1 = CR.ft.ft, i2 = CR.ft.sd, i3 = CR.sd;
					
//					cerr << i1 << " " << i2 << " " << i3 << '\n';
//					cerr << col[i1][i2] << '\n';
//					cerr << col[i2][i3] << '\n';
					kol[col[i1][i2]]--;
					kol[col[i2][i3]]--;
					
					pre[i3] = i1;
					nx[i1] = i3;
					
					st[col[i2][i3]][col[i3][nx[i3]]].erase(MP3(i2, i3, nx[i3]));
					st[col[pre[i1]][i1]][col[i1][i2]].erase(MP3(pre[i1], i1, i2));
					
					col[i1][i3] = MEX(col[i1][i2], col[i2][i3]);
					kol[col[i1][i3]]++;
					vc.PB(MP3(i1, i3, col[i1][i3]));
					
					st[col[pre[i1]][i1]][col[i1][i3]].insert(MP3(pre[i1], i1, i3));
					st[col[i1][i3]][col[i3][nx[i3]]].insert(MP3(i1, i3, nx[i3]));
					
					break;
				}
			
			}
			if (!was)
				BAD();
		}
	}
	
	cout << "DA\n";
	
	for (pi3 x : vc)
		cout << x.ft.ft + 1 << " " << x.ft.sd + 1 << " " << x.sd + 1 << '\n';
	
	return 0;
}

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