Submission #456339

#	Time	Username	Problem	Language	Result	Execution time	Memory
456339		Jasiekstrz	Trobojnica (COCI19_trobojnica)	C++17	110 / 110	561 ms	27792 KiB

trobojnica

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=2e5;
int cnt[3];
int e[N+10];
set<int> st;
set<int> ok[3];
pair<int,int> edg[N+10];
int mex(int a,int b)
{
	if(a!=0 && b!=0)
		return 0;
	if(a!=1 && b!=1)
		return 1;
	return 2;
}
int nxt(int x)
{
	auto it=st.find(x);
	if(next(it)==st.end())
		return *st.begin();
	return *next(it);
}
int prv(int x)
{
	auto it=st.find(x);
	if(it==st.begin())
		return *prev(st.end());
	return *prev(it);
}
void er(int x)
{
	ok[edg[x].fi].erase(x);
	ok[edg[x].se].erase(x);
	return;
}
void upd(int x)
{
	er(x);
	edg[x].fi=e[prv(x)];
	edg[x].se=e[x];
	if(edg[x].fi!=edg[x].se)
	{
		ok[edg[x].fi].insert(x);
		ok[edg[x].se].insert(x);
	}
	return;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		char c;
		cin>>c;
		e[i]=c-'1';
		cnt[c-'1']++;
		st.insert(i);
	}
	for(int i=0;i<3;i++)
	{
		if(cnt[i]%2!=n%2 || cnt[i]>n-2)
		{
			cout<<"NE\n";
			return 0;
		}
	}
	cout<<"DA\n";
	for(int i=1;i<=n;i++)
		upd(i);
	while(st.size()>3)
	{
		int mx=0;
		for(int i=0;i<3;i++)
		{
			if(cnt[i]>cnt[mx])
				mx=i;
		}
		int x=*ok[mx].begin();
		int c=mex(edg[x].fi,edg[x].se);
		cout<<prv(x)<<" "<<nxt(x)<<" "<<c+1<<"\n";
		for(int i=0;i<3;i++)
			cnt[i]--;
		cnt[c]+=2;
		e[prv(x)]=c;
		int pr=prv(x),nx=nxt(x);
		er(x);
		st.erase(x);
		upd(pr);
		upd(nx);
	}
	return 0;
}

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