oj.uz

Submission #456339

# Submission time Handle Problem Language Result Execution time Memory
456339 2021-08-06T13:28:21 Z Jasiekstrz Trobojnica (COCI19_trobojnica) C++17
110 / 110
 561 ms 27792 KB 
#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.0 / 20.0

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

Subtask #2
40.0 / 40.0

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

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 1 ms 324 KB Output is correct
16 Correct 2 ms 460 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 2 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 305 ms 15448 KB Output is correct
22 Correct 272 ms 14264 KB Output is correct
23 Correct 1 ms 204 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Correct 561 ms 27792 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 256 ms 13848 KB Output is correct
28 Correct 56 ms 10552 KB Output is correct
29 Correct 0 ms 204 KB Output is correct
30 Correct 55 ms 10612 KB Output is correct