| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1012601 |
2024-07-02T11:26:31 Z |
pcc |
None (JOI16_memory2) |
C++17 |
|
1 ms |
348 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{
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};
break;
}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);
}
exit(0);
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();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
