Submission #711250

#	Time	Username	Problem	Language	Result	Execution time	Memory
711250		dozer	Trobojnica (COCI19_trobojnica)	C++14	0 / 110	2074 ms	340 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;
	if (odd == 3 || odd == 0) 
	{
		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)
		{
			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);
			}
		}

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

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

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