oj.uz

Submission #1012599

# Submission time Handle Problem Language Result Execution time Memory
1012599 2024-07-02T11:17:45 Z pcc None (JOI16_memory2) C++17
0 / 100
 1 ms 604 KB 
#include "Memory2_lib.h"
#include <bits/stdc++.h>
using namespace std;


#define pii pair<int,int>
#define fs first
#define sc second

const int mxn = 110;
int N;
pii pre[mxn],nxt[mxn];
int cnt[mxn];
bitset<mxn> alive;

void del(int p){
	alive[p] = false;
	int tl = pre[p].fs,tr = nxt[p].fs;
	nxt[tl] = pii(tr,Flip(tl,tr));
	pre[tr] = pii(tl,nxt[tl].sc);
}

void solve(){
	memset(cnt,0,sizeof(cnt));
	int rt = 0;
	for(rt = 0;rt<N*2&&!alive[rt];rt++);
	assert(rt<N*2);
	int len = alive.count();
	int now = rt;
	cerr<<"SOLVE: ";

	do{
		cnt[nxt[now].sc]++;
		now = nxt[now].fs;
		cerr<<now<<"-"<<nxt[now].sc<<"->";
	}while(now != rt);

	cerr<<endl;

	if(len == 2){
		cerr<<"LEN = 2"<<endl;
		int mx = max_element(cnt,cnt+mxn)-cnt;
		Answer(now,nxt[now].fs,mx);
		return;
	}
	else if(len == 4){
		cerr<<"LEN = 4"<<endl;
		do{
			int tmp = nxt[now].sc;
			cerr<<now<<' '<<nxt[now].fs<<":"<<tmp<<"::"<<cnt[tmp]<<endl;
			if(cnt[tmp] == 1){
				Answer(now,nxt[now].fs,tmp);
				now = nxt[nxt[now].fs].fs;
				Answer(now,nxt[now].fs,nxt[now].sc);
				return;
			}
			now = nxt[now].fs;
		}while(now != rt);
		cerr<<"SYMMETRIC"<<endl;
		int other = nxt[nxt[now].fs].fs;
		Answer(now,other,Flip(now,other));
		now = nxt[now].fs,other = nxt[other].fs;
		Answer(now,other,Flip(now,other));
		return;
	}

	int mx = *max_element(cnt,cnt+mxn);

	if(mx == 4){
		vector<int> v;
		for(int tar = 0;tar<N;tar++){
			if(cnt[tar] != 4)continue;
			while(pre[now].sc == tar)now = nxt[now].fs;
			rt = now;
			do{
				pii t1 = nxt[now];pii t2 = nxt[t1.fs];pii t3 = nxt[t2.fs];pii t4 = nxt[t3.fs];
				if(t1.sc != tar||t2.sc != tar||t3.sc != tar||t4.sc != tar){
					now = nxt[now].fs;
					continue;
				}
				v = {now,t1.fs,t2.fs,t3.fs,t4.fs};
			}while(now != rt);
			cerr<<"V:";for(auto &i:v)cerr<<i<<',';cerr<<endl;
			assert(v.size() == 5);
			Answer(v[1],v[3],tar);
			del(v[1]);
			del(v[3]);
			solve();
			return;
		}
	}
	else{
		assert(mx == 3);
		for(int tar = 0;tar<N;tar++){
			if(cnt[tar] != 3)continue;
			deque<int> dq;
			do{
				pii t1 = nxt[now];
				pii t2 = nxt[t1.fs];
				pii t3 = nxt[t2.fs];
				if(t1.sc != tar||t2.sc != tar||t3.sc != tar){
					now = nxt[now].fs;
					continue;
				}
				dq = {now,t1.fs,t2.fs,t3.fs};
				break;
			}while(now != rt);
			cerr<<"DQ: ";for(auto &i:dq)cerr<<i<<',';cerr<<endl;
			assert(dq.size() == 4);
			if(Flip(dq[0],dq[3]) != tar){
				Answer(dq[1],dq[2],tar);
				del(dq[1]);
				del(dq[2]);
				solve();
				return;
			}
			else if(Flip(dq[0],dq[2]) != tar){
				Answer(dq[1],dq[3],tar);
				del(dq[1]);
				del(dq[3]);
				solve();
				return;
			}
			else{
				Answer(dq[0],dq[2],tar);
				del(dq[0]);
				del(dq[2]);
				solve();
				return;
			}

		}
		assert(false);
	}

	return;
	assert(false);
}

void Solve(int T, int NN){
	N = NN;
	for(int i = 0;i<N*2;i++)alive[i] = true;
	for(int i = 1;i<N*2;i++){
		pre[i] = pii(i-1,Flip(i-1,i));
		nxt[i-1] = pii(i,pre[i].sc);
	}
	pre[0] = pii(N*2-1,Flip(0,N*2-1));
	nxt[N*2-1] = pii(0,pre[0].sc);
	solve();
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -