oj.uz

Submission #1012605

# Submission time Handle Problem Language Result Execution time Memory
1012605 2024-07-02T11:32:05 Z pcc None (JOI16_memory2) C++17
100 / 100
 13 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);
	cerr<<"MX:" <<mx<<endl;

	if(mx == 4){
		cerr<<"FOUR"<<endl;
		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{
				if(pre[now].sc != tar&&nxt[now].sc == tar)v.push_back(nxt[now].fs);
				else if(pre[now].sc == tar&&nxt[now].sc != tar)v.push_back(pre[now].fs);
				now = nxt[now].fs;
			}while(now != rt);
			sort(v.begin(),v.end());v.resize(unique(v.begin(),v.end())-v.begin());
			cerr<<"V:";for(auto &i:v)cerr<<i<<',';cerr<<endl;
			if(v.size() != 2)exit(0);
			assert(v.size() == 2);
			Answer(v[0],v[1],tar);
			del(v[0]);
			del(v[1]);
			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);
			if(dq.empty())continue;
			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);
	}

	assert(false);
	return;
}

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);
	cerr<<"IN SOLVE"<<endl;
	solve();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Output is correct
2 Correct 11 ms 456 KB Output is correct
3 Correct 11 ms 348 KB Output is correct
4 Correct 11 ms 440 KB Output is correct
5 Correct 11 ms 348 KB Output is correct
6 Correct 12 ms 348 KB Output is correct
7 Correct 11 ms 440 KB Output is correct
8 Correct 11 ms 348 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 448 KB Output is correct
2 Correct 11 ms 448 KB Output is correct
3 Correct 11 ms 344 KB Output is correct
4 Correct 11 ms 456 KB Output is correct
5 Correct 11 ms 348 KB Output is correct
6 Correct 11 ms 604 KB Output is correct
7 Correct 11 ms 348 KB Output is correct
8 Correct 11 ms 480 KB Output is correct
9 Correct 11 ms 348 KB Output is correct
10 Correct 12 ms 440 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 348 KB Output is correct
2 Correct 11 ms 348 KB Output is correct
3 Correct 11 ms 348 KB Output is correct
4 Correct 11 ms 448 KB Output is correct
5 Correct 13 ms 444 KB Output is correct
6 Correct 10 ms 348 KB Output is correct
7 Correct 11 ms 452 KB Output is correct
8 Correct 9 ms 516 KB Output is correct
9 Correct 11 ms 344 KB Output is correct
10 Correct 10 ms 348 KB Output is correct