Submission #1012580

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012580		pcc	Memory 2 (JOI16_memory2)	C++17	0 / 100	1 ms	348 KiB

memory2

#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 p = max_element(cnt,cnt+mxn)-cnt;

	if(cnt[p] == 4){
		vector<int> v;
		while(pre[now].sc == p)now = nxt[now].fs;
		do{
			if(pre[now].sc == p&&nxt[now].sc == p)v.push_back(now);
			now = nxt[now].fs;
		}while(now != rt);
		cerr<<"V:";for(auto &i:v)cerr<<i<<',';cerr<<endl;
		assert(v.size() == 3);
		Answer(v[0],v[2],p);
		del(v[0]);
		del(v[2]);
		solve();
		return;
	}
	else{
		assert(cnt[p] == 3);
		deque<int> dq;
		do{
			if(pre[now].sc == p||nxt[now].sc == p)dq.push_back(now);
			now = nxt[now].fs;
		}while(now != rt);
		cerr<<"DQ: ";for(auto &i:dq)cerr<<i<<',';cerr<<endl;
		assert(dq.size() == 4);
		while(pre[dq.front()].sc == p){
			dq.push_back(dq.front());
			dq.pop_front();
		}
		if(Flip(dq[0],dq[3]) != p){
			Answer(dq[1],dq[2],p);
			del(dq[1]);
			del(dq[2]);
			solve();
			return;
		}
		else if(Flip(dq[0],dq[2]) != p){
			Answer(dq[1],dq[3],p);
			del(dq[1]);
			del(dq[3]);
			solve();
			return;
		}
		else{
			Answer(dq[0],dq[2],p);
			del(dq[0]);
			del(dq[2]);
			solve();
			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
• Subtask 2: 0 / 50
• Subtask 3: 0 / 40