QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#321923 | #8215. Isomorphic Delight | yyyyxh | WA | 38ms | 88584kb | C++23 | 3.7kb | 2024-02-05 21:48:27 | 2024-02-05 21:48:28 |
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];
int ff[S],diam;
void calc(int p){
dp[p]=0;ff[p]=0;
for(int x:adj[p]){
calc(x);
diam=max(ff[p]+ff[x]+1,diam);
ff[p]=max(ff[p],ff[x]+1);
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(){
diam=0;
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(tt==8) tt=5;
if(cc==1&&ccc==3&&diam==num-2) 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: 4ms
memory: 7792kb
input:
1
output:
YES 0
result:
ok Everything ok
Test #2:
score: 0
Accepted
time: 3ms
memory: 6940kb
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: 3ms
memory: 6748kb
input:
4
output:
NO
result:
ok Everything ok
Test #4:
score: 0
Accepted
time: 3ms
memory: 7552kb
input:
2
output:
NO
result:
ok Everything ok
Test #5:
score: 0
Accepted
time: 3ms
memory: 6072kb
input:
3
output:
NO
result:
ok Everything ok
Test #6:
score: 0
Accepted
time: 4ms
memory: 7540kb
input:
5
output:
NO
result:
ok Everything ok
Test #7:
score: 0
Accepted
time: 3ms
memory: 6280kb
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: 16ms
memory: 86708kb
input:
8
output:
YES 6 2 3 2 6 2 8 3 4 4 5 6 7
result:
ok Everything ok
Test #9:
score: 0
Accepted
time: 20ms
memory: 85676kb
input:
9
output:
YES 7 2 3 2 6 2 8 3 4 4 5 6 7 5 9
result:
ok Everything ok
Test #10:
score: 0
Accepted
time: 28ms
memory: 84224kb
input:
10
output:
YES 8 2 3 2 6 2 8 3 4 4 5 6 7 5 9 9 10
result:
ok Everything ok
Test #11:
score: 0
Accepted
time: 11ms
memory: 87156kb
input:
11
output:
YES 9 2 3 2 6 2 8 3 4 4 5 6 7 5 9 9 10 10 11
result:
ok Everything ok
Test #12:
score: 0
Accepted
time: 24ms
memory: 85736kb
input:
12
output:
YES 10 2 3 2 6 2 8 3 4 4 5 6 7 5 9 9 10 10 11 11 12
result:
ok Everything ok
Test #13:
score: 0
Accepted
time: 11ms
memory: 87116kb
input:
13
output:
YES 11 2 3 2 6 2 8 3 4 4 5 6 7 5 9 9 10 10 11 11 12 12 13
result:
ok Everything ok
Test #14:
score: 0
Accepted
time: 32ms
memory: 86416kb
input:
14
output:
YES 12 2 3 2 6 2 8 3 4 4 5 6 7 5 9 9 10 10 11 11 12 12 13 13 14
result:
ok Everything ok
Test #15:
score: 0
Accepted
time: 24ms
memory: 84400kb
input:
15
output:
YES 13 2 3 2 6 2 8 3 4 4 5 6 7 5 9 9 10 10 11 11 12 12 13 13 14 14 15
result:
ok Everything ok
Test #16:
score: 0
Accepted
time: 20ms
memory: 87080kb
input:
16
output:
YES 13 2 3 2 6 2 8 3 4 4 5 6 7 9 10 9 14 10 11 10 13 11 12 14 15 15 16
result:
ok Everything ok
Test #17:
score: 0
Accepted
time: 30ms
memory: 86492kb
input:
17
output:
YES 14 2 3 2 6 2 8 3 4 4 5 6 7 9 10 9 14 10 11 10 13 11 12 14 15 15 16 16 17
result:
ok Everything ok
Test #18:
score: 0
Accepted
time: 12ms
memory: 86064kb
input:
18
output:
YES 15 2 3 2 6 2 8 3 4 4 5 6 7 9 10 9 14 10 11 10 13 11 12 14 15 15 16 16 17 17 18
result:
ok Everything ok
Test #19:
score: 0
Accepted
time: 32ms
memory: 85988kb
input:
19
output:
YES 16 2 3 2 6 2 8 3 4 4 5 6 7 9 10 9 14 10 11 10 13 11 12 14 15 15 16 16 17 17 18 18 19
result:
ok Everything ok
Test #20:
score: 0
Accepted
time: 23ms
memory: 86844kb
input:
598
output:
YES 544 2 3 2 6 2 8 3 4 4 5 6 7 9 10 9 14 10 11 10 13 11 12 14 15 15 16 17 18 17 22 17 25 18 19 18 21 19 20 22 23 23 24 26 27 26 31 26 34 27 28 28 29 29 30 31 32 32 33 35 36 35 40 36 37 37 38 38 39 40 41 40 43 41 42 44 45 44 49 44 52 45 46 45 48 46 47 49 50 50 51 52 53 54 55 54 59 54 62 55 56 56 57 ...
result:
ok Everything ok
Test #21:
score: 0
Accepted
time: 28ms
memory: 86148kb
input:
245
output:
YES 221 2 3 2 6 2 8 3 4 4 5 6 7 9 10 9 14 10 11 10 13 11 12 14 15 15 16 17 18 17 22 17 25 18 19 18 21 19 20 22 23 23 24 26 27 26 31 26 34 27 28 28 29 29 30 31 32 32 33 35 36 35 40 36 37 37 38 38 39 40 41 40 43 41 42 44 45 44 49 44 52 45 46 45 48 46 47 49 50 50 51 52 53 54 55 54 59 54 62 55 56 56 57 ...
result:
ok Everything ok
Test #22:
score: 0
Accepted
time: 26ms
memory: 87260kb
input:
793
output:
YES 724 2 3 2 6 2 8 3 4 4 5 6 7 9 10 9 14 10 11 10 13 11 12 14 15 15 16 17 18 17 22 17 25 18 19 18 21 19 20 22 23 23 24 26 27 26 31 26 34 27 28 28 29 29 30 31 32 32 33 35 36 35 40 36 37 37 38 38 39 40 41 40 43 41 42 44 45 44 49 44 52 45 46 45 48 46 47 49 50 50 51 52 53 54 55 54 59 54 62 55 56 56 57 ...
result:
ok Everything ok
Test #23:
score: 0
Accepted
time: 16ms
memory: 86200kb
input:
133
output:
YES 119 2 3 2 6 2 8 3 4 4 5 6 7 9 10 9 14 10 11 10 13 11 12 14 15 15 16 17 18 17 22 17 25 18 19 18 21 19 20 22 23 23 24 26 27 26 31 26 34 27 28 28 29 29 30 31 32 32 33 35 36 35 40 36 37 37 38 38 39 40 41 40 43 41 42 44 45 44 49 44 52 45 46 45 48 46 47 49 50 50 51 52 53 54 55 54 59 54 62 55 56 56 57 ...
result:
ok Everything ok
Test #24:
score: 0
Accepted
time: 32ms
memory: 87228kb
input:
681
output:
YES 620 2 3 2 6 2 8 3 4 4 5 6 7 9 10 9 14 10 11 10 13 11 12 14 15 15 16 17 18 17 22 17 25 18 19 18 21 19 20 22 23 23 24 26 27 26 31 26 34 27 28 28 29 29 30 31 32 32 33 35 36 35 40 36 37 37 38 38 39 40 41 40 43 41 42 44 45 44 49 44 52 45 46 45 48 46 47 49 50 50 51 52 53 54 55 54 59 54 62 55 56 56 57 ...
result:
ok Everything ok
Test #25:
score: 0
Accepted
time: 19ms
memory: 86852kb
input:
922
output:
YES 843 2 3 2 6 2 8 3 4 4 5 6 7 9 10 9 14 10 11 10 13 11 12 14 15 15 16 17 18 17 22 17 25 18 19 18 21 19 20 22 23 23 24 26 27 26 31 26 34 27 28 28 29 29 30 31 32 32 33 35 36 35 40 36 37 37 38 38 39 40 41 40 43 41 42 44 45 44 49 44 52 45 46 45 48 46 47 49 50 50 51 52 53 54 55 54 59 54 62 55 56 56 57 ...
result:
ok Everything ok
Test #26:
score: 0
Accepted
time: 20ms
memory: 86672kb
input:
876
output:
YES 800 2 3 2 6 2 8 3 4 4 5 6 7 9 10 9 14 10 11 10 13 11 12 14 15 15 16 17 18 17 22 17 25 18 19 18 21 19 20 22 23 23 24 26 27 26 31 26 34 27 28 28 29 29 30 31 32 32 33 35 36 35 40 36 37 37 38 38 39 40 41 40 43 41 42 44 45 44 49 44 52 45 46 45 48 46 47 49 50 50 51 52 53 54 55 54 59 54 62 55 56 56 57 ...
result:
ok Everything ok
Test #27:
score: 0
Accepted
time: 19ms
memory: 85748kb
input:
7740
output:
YES 7191 2 3 2 6 2 8 3 4 4 5 6 7 9 10 9 14 10 11 10 13 11 12 14 15 15 16 17 18 17 22 17 25 18 19 18 21 19 20 22 23 23 24 26 27 26 31 26 34 27 28 28 29 29 30 31 32 32 33 35 36 35 40 36 37 37 38 38 39 40 41 40 43 41 42 44 45 44 49 44 52 45 46 45 48 46 47 49 50 50 51 52 53 54 55 54 59 54 62 55 56 56 57...
result:
ok Everything ok
Test #28:
score: 0
Accepted
time: 23ms
memory: 88180kb
input:
2460
output:
YES 2268 2 3 2 6 2 8 3 4 4 5 6 7 9 10 9 14 10 11 10 13 11 12 14 15 15 16 17 18 17 22 17 25 18 19 18 21 19 20 22 23 23 24 26 27 26 31 26 34 27 28 28 29 29 30 31 32 32 33 35 36 35 40 36 37 37 38 38 39 40 41 40 43 41 42 44 45 44 49 44 52 45 46 45 48 46 47 49 50 50 51 52 53 54 55 54 59 54 62 55 56 56 57...
result:
ok Everything ok
Test #29:
score: 0
Accepted
time: 20ms
memory: 86400kb
input:
7533
output:
YES 6998 2 3 2 6 2 8 3 4 4 5 6 7 9 10 9 14 10 11 10 13 11 12 14 15 15 16 17 18 17 22 17 25 18 19 18 21 19 20 22 23 23 24 26 27 26 31 26 34 27 28 28 29 29 30 31 32 32 33 35 36 35 40 36 37 37 38 38 39 40 41 40 43 41 42 44 45 44 49 44 52 45 46 45 48 46 47 49 50 50 51 52 53 54 55 54 59 54 62 55 56 56 57...
result:
ok Everything ok
Test #30:
score: 0
Accepted
time: 24ms
memory: 84476kb
input:
5957
output:
YES 5527 2 3 2 6 2 8 3 4 4 5 6 7 9 10 9 14 10 11 10 13 11 12 14 15 15 16 17 18 17 22 17 25 18 19 18 21 19 20 22 23 23 24 26 27 26 31 26 34 27 28 28 29 29 30 31 32 32 33 35 36 35 40 36 37 37 38 38 39 40 41 40 43 41 42 44 45 44 49 44 52 45 46 45 48 46 47 49 50 50 51 52 53 54 55 54 59 54 62 55 56 56 57...
result:
ok Everything ok
Test #31:
score: 0
Accepted
time: 28ms
memory: 88584kb
input:
92651
output:
YES 87225 2 3 2 6 2 8 3 4 4 5 6 7 9 10 9 14 10 11 10 13 11 12 14 15 15 16 17 18 17 22 17 25 18 19 18 21 19 20 22 23 23 24 26 27 26 31 26 34 27 28 28 29 29 30 31 32 32 33 35 36 35 40 36 37 37 38 38 39 40 41 40 43 41 42 44 45 44 49 44 52 45 46 45 48 46 47 49 50 50 51 52 53 54 55 54 59 54 62 55 56 56 5...
result:
ok Everything ok
Test #32:
score: 0
Accepted
time: 33ms
memory: 87128kb
input:
58779
output:
YES 55235 2 3 2 6 2 8 3 4 4 5 6 7 9 10 9 14 10 11 10 13 11 12 14 15 15 16 17 18 17 22 17 25 18 19 18 21 19 20 22 23 23 24 26 27 26 31 26 34 27 28 28 29 29 30 31 32 32 33 35 36 35 40 36 37 37 38 38 39 40 41 40 43 41 42 44 45 44 49 44 52 45 46 45 48 46 47 49 50 50 51 52 53 54 55 54 59 54 62 55 56 56 5...
result:
ok Everything ok
Test #33:
score: 0
Accepted
time: 27ms
memory: 87968kb
input:
12203
output:
YES 11374 2 3 2 6 2 8 3 4 4 5 6 7 9 10 9 14 10 11 10 13 11 12 14 15 15 16 17 18 17 22 17 25 18 19 18 21 19 20 22 23 23 24 26 27 26 31 26 34 27 28 28 29 29 30 31 32 32 33 35 36 35 40 36 37 37 38 38 39 40 41 40 43 41 42 44 45 44 49 44 52 45 46 45 48 46 47 49 50 50 51 52 53 54 55 54 59 54 62 55 56 56 5...
result:
ok Everything ok
Test #34:
score: -100
Wrong Answer
time: 38ms
memory: 86696kb
input:
55627
output:
YES 52258 2 3 2 6 2 8 3 4 4 5 6 7 9 10 9 14 10 11 10 13 11 12 14 15 15 16 17 18 17 22 17 25 18 19 18 21 19 20 22 23 23 24 26 27 26 31 26 34 27 28 28 29 29 30 31 32 32 33 35 36 35 40 36 37 37 38 38 39 40 41 40 43 41 42 44 45 44 49 44 52 45 46 45 48 46 47 49 50 50 51 52 53 54 55 54 59 54 62 55 56 56 5...
result:
wrong answer Not asymmetric