QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#321910 | #8215. Isomorphic Delight | yyyyxh | WA | 29ms | 79464kb | C++23 | 3.6kb | 2024-02-05 21:33:34 | 2024-02-05 21:33:35 |
Judging History
answer
#include <cstdio>
#include <vector>
#include <random>
#include <numeric>
#include <algorithm>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
typedef unsigned long long ull;
const int N=2000003;
const int S=53;
__gnu_pbds::gp_hash_table<ull,bool> del;
mt19937 rng(random_device{}());
int n,sum;
int su[N],sv[N],tp;
void add(int u,int v){++tp;su[tp]=u;sv[tp]=v;}
vector<int> sn[N];
int sz[N],cnt;
bool f[N][S],vis[N][S];
int g[N][S];
vector<int> cur;
int len;
struct TreeHash{
ull p[4][65536];
TreeHash(){for(int t=0;t<4;++t) iota(p[t],p[t]+65536,0),shuffle(p[t],p[t]+65536,rng);}
ull Hs(ull x){
ull res=0;
res=res<<16|p[0][x>>(0*16)&65535];
res=res<<16|p[1][x>>(1*16)&65535];
res=res<<16|p[2][x>>(2*16)&65535];
res=res<<16|p[3][x>>(3*16)&65535];
return res;
};
ull operator()(ull x){x=Hs(x^(x<<13)^(x>>17));return Hs((x<<3)^(x>>5)^(x<<7));}
}H;
bool dfs(int x,int s){
if(vis[x][s]&&!f[x][s]) return 0;
if(vis[x][s]&&g[x][s]<x) return dfs(g[x][s],s);
vis[x][s]=1;
if(!x){
if(!s){
sn[++cnt]=cur;
sz[cnt]=len;
return f[x][s]=1;
}
else return f[x][s]=0;
}
if(dfs(x-1,s)) f[x][s]=1;
if(s>=sz[x]){
cur.emplace_back(x);
if(dfs(x-1,s-sz[x])) f[x][s]=1,g[x][s]=x;
else g[x][s]=g[x-1][s];
cur.pop_back();
}
else g[x][s]=g[x-1][s];
return f[x][s];
}
int num,las;
vector<int> adj[S];
int build(int p){
int t=++num;
for(int x:sn[p]) adj[t].emplace_back(build(x));
return t;
}
void trav(int p){
for(int x:adj[p]){
trav(x);
printf("%d -> %d\n",p,x);
}
}
void output(){
while(sum<n) add(las,++sum),las=sum;
printf("%d\n",tp);
for(int i=1;i<=tp;++i) printf("%d %d\n",su[i],sv[i]);
exit(0);
}
ull dp[S];
void calc(int p){
dp[p]=0;
for(int x:adj[p]){
calc(x);
dp[p]+=H(dp[x]);
}
}
void recalc(int p){
for(int x:adj[p]){
dp[x]+=H(dp[p]-H(dp[x]));
recalc(x);
}
}
bool check(){
calc(1);recalc(1);
sort(dp+1,dp+num+1);
for(int i=1;i<num;++i) if(dp[i]==dp[i+1]) return 0;
ull cur=accumulate(dp+1,dp+num+1,0llu);
if(del[cur]) return 0;
del[cur]=1;
int cc=0,ccc=0,tt=0;
for(int i=1;i<=num;++i){
if(adj[i].size()+(i!=1)==3lu) ++cc;
if(adj[i].size()+(i!=1)==1lu) ++ccc,tt=i+sum;
}
if(cc==1&&ccc==3) las=tt;
return 1;
}
void solve(){
num=1;
for(int x:cur) adj[1].emplace_back(build(x));
if(check()){
for(int i=1;i<=num;++i)
for(int j:adj[i]) add(sum+i,sum+j);
sum+=num;
if(sum==n) output();
}
for(int i=1;i<=num;++i) adj[i].clear();
}
bool go(int x,int s){
if(vis[x][s]&&!f[x][s]) return 0;
if(vis[x][s]&&g[x][s]<x) return go(g[x][s],s);
if(sum+len>n) output();
vis[x][s]=1;
if(!x){
if(!s){
solve();
return f[x][s]=1;
}
else return f[x][s]=0;
}
if(go(x-1,s)) f[x][s]=1;
if(s>=sz[x]){
cur.emplace_back(x);
if(go(x-1,s-sz[x])) f[x][s]=1,g[x][s]=x;
else g[x][s]=g[x-1][s];
cur.pop_back();
}
else g[x][s]=g[x-1][s];
return f[x][s];
}
int main(){
scanf("%d",&n);
if(n==1){
puts("YES");
puts("0");
return 0;
}
if(n<=5){
puts("NO");
return 0;
}
if(n==6){
puts("YES");
puts("6");
puts("1 2");
puts("2 3");
puts("1 3");
puts("3 4");
puts("2 5");
puts("5 6");
return 0;
}
if(n==7){
puts("YES");
printf("%d\n",n-1);
for(int i=2;i<n;++i) printf("%d %d\n",i-1,i);
printf("3 %d\n",n);
return 0;
}
puts("YES");
sz[cnt=1]=1;
for(int i=1;i<=18;++i){
len=i+1;
dfs(cnt,i);
}
for(int i=1,t=1;;++i){
len=i;
while(t<=cnt&&sz[t]*2<=i) ++t;
go(t-1,i-1);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5732kb
input:
1
output:
YES 0
result:
ok Everything ok
Test #2:
score: 0
Accepted
time: 4ms
memory: 5676kb
input:
6
output:
YES 6 1 2 2 3 1 3 3 4 2 5 5 6
result:
ok Everything ok
Test #3:
score: 0
Accepted
time: 4ms
memory: 5792kb
input:
4
output:
NO
result:
ok Everything ok
Test #4:
score: 0
Accepted
time: 4ms
memory: 5996kb
input:
2
output:
NO
result:
ok Everything ok
Test #5:
score: 0
Accepted
time: 4ms
memory: 6008kb
input:
3
output:
NO
result:
ok Everything ok
Test #6:
score: 0
Accepted
time: 4ms
memory: 5684kb
input:
5
output:
NO
result:
ok Everything ok
Test #7:
score: 0
Accepted
time: 4ms
memory: 6140kb
input:
7
output:
YES 6 1 2 2 3 3 4 4 5 5 6 3 7
result:
ok Everything ok
Test #8:
score: 0
Accepted
time: 27ms
memory: 79180kb
input:
8
output:
YES 6 2 3 2 6 2 8 3 4 4 5 6 7
result:
ok Everything ok
Test #9:
score: -100
Wrong Answer
time: 29ms
memory: 79464kb
input:
9
output:
YES 7 2 3 2 6 2 8 3 4 4 5 6 7 8 9
result:
wrong answer Not asymmetric