oj.uz

답안 #439470

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
439470 2021-06-30T05:21:39 Z negar_a Trobojnica (COCI19_trobojnica) C++14
0 / 110
 22 ms 24268 KB 
//!yrt tsuj uoy srettam gnihton no emoc
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define pii pair <int, int>
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define F first
#define S second

const int maxn = 5e5 + 5;
struct edge{
	int c, l, r, u, v;
} ed[maxn];
int t[5];
vector <int> vec[maxn];
bool mark[maxn];
int cnt;

int find_mx(){
	pii v[] = {{t[0], 0}, {t[1], 1}, {t[2], 2}};
	sort(v, v + 3);
	return v[2].S;
}
void upd(int le, int x){
	ed[cnt].c = 2 * (ed[x].c + ed[le].c) % 3;
	ed[cnt].l = ed[le].l;
	ed[cnt].r = ed[x].r;
	ed[cnt].u = ed[le].u;
	ed[cnt].v = ed[x].v;
	cout << ed[cnt].u + 1 << " " << ed[cnt].v + 1 << " " << ed[cnt].c + 1 << endl;
	mark[x] = mark[le] = true;
	vec[ed[cnt].c].pb(cnt);
	vec[ed[ed[cnt].l].c].pb(ed[cnt].l);
	vec[ed[ed[cnt].r].c].pb(ed[cnt].r);
	t[ed[cnt].c] ++;
	t[ed[le].c] --;
	t[ed[x].c] --;
	cnt ++;
	return;
}
bool check(int x){
	if(mark[x]){
		return false;
	}
	int le = ed[x].l;
	int ri = ed[x].r;
	if(ed[x].c != ed[le].c && !mark[le]){
		upd(le, x);
		return true;
	}
	if(ed[x].c != ed[ri].c && !mark[ri]){
		upd(x, ri);
		return true;
	}
	return false;
}
void solve(int n){
	if(n == 3){
		return;
	}
	int mx = find_mx();
	bool f = true;
	while(f){
		int x = vec[mx].back();
		vec[mx].pop_back();
		if(check(x)){
			f = false;
		}
	}
	solve(n - 1);
}

int main(){
	fast_io;
	int n;
	cin >> n;
	string s; cin >> s;
	for(int i = 0; i < n; i ++){
		ed[i].c = (s[i] - '0') - 1;
		ed[i].u = i;
		ed[i].v = (i + 1) % n;
		ed[i].l = (i - 1 + n) % n;
		ed[i].r = (i + 1) % n;
		t[ed[i].c] ++;
		vec[ed[i].c].pb(i);
	}
	for(int i = 0; i < 3; i ++){
		if((t[i] & 1) != (n & 1) || t[i] == n){
			cout << "NE";
			return 0;
		}
	}
	cnt = n;
	cout << "DA" << endl;
	solve(n);
	
	return 0;
}

Subtask #1
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 11980 KB Output is correct
2 Correct 8 ms 11980 KB Output is correct
3 Runtime error 22 ms 24268 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 11980 KB Output is correct
2 Correct 8 ms 11980 KB Output is correct
3 Runtime error 22 ms 24268 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 11980 KB Output is correct
2 Correct 8 ms 11980 KB Output is correct
3 Runtime error 22 ms 24268 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -