oj.uz

Submission #711255

# Submission time Handle Problem Language Result Execution time Memory
711255 2023-03-16T11:37:23 Z dozer Trobojnica (COCI19_trobojnica) C++14
110 / 110
 234 ms 21828 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 2 ms 336 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 2 ms 336 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 464 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 2 ms 336 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 2 ms 336 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 464 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 162 ms 17996 KB Output is correct
22 Correct 167 ms 14544 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 234 ms 21828 KB Output is correct
26 Correct 0 ms 212 KB Output is correct
27 Correct 107 ms 11072 KB Output is correct
28 Correct 168 ms 20244 KB Output is correct
29 Correct 1 ms 328 KB Output is correct
30 Correct 52 ms 12188 KB Output is correct