제출 #711255

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
711255		dozer	Trobojnica (COCI19_trobojnica)	C++14	110 / 110	234 ms	21828 KiB

trobojnica

#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n";
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define N 200005

const int modulo = 1e9 + 7;

int arr[N];


int32_t main()
{
	fastio();

	int n;
	cin>>n;
	vector<int> cnt(5, 0);
	for (int i = 0; i < n; i++)
	{
		char tmp;
		cin>>tmp;
		arr[i] = tmp - '0';
		cnt[arr[i]]++;
	}

	int odd = 0;
	for (int i = 1; i <= 3; i++) odd += cnt[i] % 2;
	
	set<int> s;
	for (int i = 0; i < n; i++) s.insert(i);
	vector<int> l(n + 5, 0), r(n + 5, 0);
	for (int i = 0; i < n; i++)
		l[i] = arr[(i - 1 + n) % n];
	for (int i = 0; i < n; i++)
		r[i] = arr[i];
	set<int> diff[5];
	for (int i = 0; i < n; i++)
		if (l[i] != r[i]) diff[6 - (r[i] + l[i])].insert(i);

	vector<array<int, 3>> ans;
	while(s.size() > 3)
	{
		int done = 0;
		for (int i = 1; i <= 3; i++)
		{
			if (diff[i].empty()) continue;
			int flag = 0;
			for (int j = 1; j <= 3; j++)
			{
				if (j == i) continue;
				if (cnt[j] == 0) flag = 1;
			}
			if (flag || cnt[1] + cnt[2] + cnt[3] - cnt[i] <= 2) continue;
			int top = *diff[i].begin();
			s.erase(top);
			diff[i].erase(top);

			int nxt = 0, prv = 0;
			auto it = s.upper_bound(top);
			if (it == s.end()) it = s.begin();
			nxt = *it;
			it = s.upper_bound(top);
			if (it == s.begin()) prv = *s.rbegin();
			else
			{
				it--;
				prv = *it;
			}
			

			ans.pb({prv + 1, nxt + 1, i});

			if (r[prv] != l[prv]) diff[6 - (r[prv] + l[prv])].erase(prv);
			if (r[nxt] != l[nxt]) diff[6 - (r[nxt] + l[nxt])].erase(nxt);

			r[prv] = i;
			l[nxt] = i;
			cnt[l[top]]--;
			cnt[r[top]]--;
			cnt[i]++;
			
			if (r[prv] != l[prv]) diff[6 - (r[prv] + l[prv])].insert(prv);
			if (r[nxt] != l[nxt]) diff[6 - (r[nxt] + l[nxt])].insert(nxt);
			done = 1;
			break;
		}
		if (done == 0)
		{
			cout<<"NE\n";
			return 0;
		}
	}

	if (cnt[1] != 1 || cnt[2] != 1 || cnt[3] != 1)
	{
		cout<<"NE\n";
		return 0;
	}

	cout<<"DA\n";
	for (auto i : ans)
	{
		for (auto j : i) cout<<j<<sp;
		cout<<endl;
	}

	cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " seconds\n";
}

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