oj.uz

Submission #442327

# Submission time Handle Problem Language Result Execution time Memory
442327 2021-07-07T13:02:23 Z minoum Trobojnica (COCI19_trobojnica) C++17
110 / 110
 279 ms 19416 KB 
#include<bits/stdc++.h>

using namespace std;
typedef long long int ll;

const int MAXN = 2e5+10;

int n, cnt[4], nxt[MAXN], nxtc[MAXN], prv[MAXN], prvc[MAXN];
string s;
vector <pair<pair<int,int>,int>> ans;
set <int> dif[4];

inline int oth(int x, int y){
	if(x!=1&&y!=1) return 1;
	if(x!=2&&y!=2) return 2;
	return 3;
}

inline void add(int i){
	if(nxtc[i]!=prvc[i]){
		dif[nxtc[i]].insert(i);
		dif[prvc[i]].insert(i);
	}
	return;
}

inline void rmv(int i){
	if(nxtc[i]!=prvc[i]){
		dif[nxtc[i]].erase(i);
		dif[prvc[i]].erase(i);
	}
	return;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> s;
	for(int i = 0; i < n; i++) cnt[s[i]-'0']++;
	if((cnt[1]%2!=n%2)||(cnt[2]%2!=n%2)||(cnt[3]%2!=n%2)||(cnt[1]==n)||(cnt[2]==n)||(cnt[3]==n)){
		cout << "NE" << endl;
		return 0;
	}
	for(int i = 1; i <= n; i++) nxt[i] = (i%n)+1, nxtc[i] = s[i-1]-'0';
	for(int i = 1; i <= n; i++){
		prv[i] = (i==1?n:i-1), prvc[i] = nxtc[prv[i]]; 
		add(i);
	} 
	while((int)ans.size()<n-3){
		int mx;
		if(cnt[1]>=cnt[2]&&cnt[1]>=cnt[3]) mx = 1;
		else mx = ((cnt[2]>=cnt[1]&&cnt[2]>=cnt[3])?2:3);
		int ind = *dif[mx].begin();
		int cc = oth(nxtc[ind],prvc[ind]), nx = nxt[ind], pr = prv[ind];
	//	cout << "mx:" << mx << "  ind:" << ind << "  nx:"<< nx << "  pr:" << pr << "  nxc:" << nxtc[ind] << "  prc:" << prvc[ind] << "  cc:" << cc << endl;
		ans.push_back({{nxt[ind],prv[ind]},cc});
		cnt[cc]++; cnt[nxtc[ind]]--; cnt[prvc[ind]]--;
		rmv(ind); rmv(nx); rmv(pr);
		nxt[pr] = nx; prv[nx] = pr;
		nxtc[pr] = cc; prvc[nx] = cc;
		add(nx); add(pr);
	}
	cout << "DA" << endl;
	for(auto i: ans) cout << i.first.first << " " << i.first.second << " " << i.second << '\n';
	return 0; 
}

Subtask #1
20.0 / 20.0

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

Subtask #2
40.0 / 40.0

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

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 320 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 0 ms 320 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 320 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 2 ms 332 KB Output is correct
17 Correct 0 ms 332 KB Output is correct
18 Correct 2 ms 332 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 2 ms 332 KB Output is correct
21 Correct 126 ms 9476 KB Output is correct
22 Correct 99 ms 8408 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 279 ms 19416 KB Output is correct
26 Correct 1 ms 204 KB Output is correct
27 Correct 126 ms 9756 KB Output is correct
28 Correct 2 ms 844 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 2 ms 844 KB Output is correct