Submission #439471

#	Time	Username	Problem	Language	Result	Execution time	Memory
439471		negar_a	Trobojnica (COCI19_trobojnica)	C++14	110 / 110	414 ms	26236 KiB

trobojnica

//!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;
	ed[ed[cnt].l].r = cnt;
	ed[ed[cnt].r].l = cnt;
	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;
}

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