QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#321941 | #8215. Isomorphic Delight | yyyyxh | TL | 1276ms | 8396kb | C++23 | 4.0kb | 2024-02-05 22:30:12 | 2024-02-05 22:30:12 |
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(){
// printf("%d\n",n-sum);
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);
}
}
vector<int> ss[N];
int mx,tt;
void find(int p,int ft,int d){
if(d>mx) mx=d,tt=p;
for(int x:ss[p]){
if(x==ft) continue;
find(x,p,d+1);
}
}
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,rt=0;
for(int i=1;i<=num;++i){
if(adj[i].size()+(i!=1)==3lu){rt=i;++cc;}
if(adj[i].size()+(i!=1)==1lu) ++ccc;
}
if(cc==1&&ccc==3&&diam==num-2){
for(int i=1;i<=num;++i)
for(int j:adj[i]){
ss[i].emplace_back(j);
ss[j].emplace_back(i);
}
mx=0;
find(rt,0,0);
las=tt+sum;
for(int i=1;i<=num;++i) ss[i].clear();
}
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,t=1;;++i){
if(i&1){
len=(i>>1)+1;
dfs(cnt,i>>1);
}
len=i;
while(t<=cnt&&sz[t]*2<=i) ++t;
go(t-1,i-1);
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 6ms
memory: 7168kb
input:
1
output:
YES 0
result:
ok Everything ok
Test #2:
score: 0
Accepted
time: 5ms
memory: 6124kb
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: 6ms
memory: 7264kb
input:
4
output:
NO
result:
ok Everything ok
Test #4:
score: 0
Accepted
time: 5ms
memory: 6396kb
input:
2
output:
NO
result:
ok Everything ok
Test #5:
score: 0
Accepted
time: 5ms
memory: 7324kb
input:
3
output:
NO
result:
ok Everything ok
Test #6:
score: 0
Accepted
time: 5ms
memory: 5796kb
input:
5
output:
NO
result:
ok Everything ok
Test #7:
score: 0
Accepted
time: 5ms
memory: 5876kb
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: 3ms
memory: 6164kb
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: 5ms
memory: 5904kb
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: 6ms
memory: 6180kb
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: 5ms
memory: 5904kb
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: 3ms
memory: 5904kb
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: 5ms
memory: 6156kb
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: 2ms
memory: 5956kb
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: 6ms
memory: 5960kb
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: 3ms
memory: 5892kb
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: 0ms
memory: 5900kb
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: 0ms
memory: 5892kb
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: 5ms
memory: 5888kb
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: 3ms
memory: 5924kb
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: 6ms
memory: 5916kb
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: 8ms
memory: 5940kb
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: 6ms
memory: 6872kb
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: 8ms
memory: 7100kb
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: 9ms
memory: 8004kb
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: 8ms
memory: 7076kb
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: 46ms
memory: 8396kb
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: 10ms
memory: 7160kb
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: 45ms
memory: 6136kb
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: 39ms
memory: 6020kb
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: 1170ms
memory: 7344kb
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: 629ms
memory: 6856kb
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: 83ms
memory: 6216kb
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: 0
Accepted
time: 583ms
memory: 6836kb
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:
ok Everything ok
Test #35:
score: 0
Accepted
time: 1276ms
memory: 7372kb
input:
99051
output:
YES 93269 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 #36:
score: -100
Time Limit Exceeded
input:
811713