QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#321911 | #8215. Isomorphic Delight | yyyyxh | WA | 41ms | 79460kb | C++23 | 3.6kb | 2024-02-05 21:34:51 | 2024-02-05 21:34:51 |
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(tt==8) tt=5;
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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 4ms
memory: 5996kb
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: 5664kb
input:
4
output:
NO
result:
ok Everything ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 5996kb
input:
2
output:
NO
result:
ok Everything ok
Test #5:
score: 0
Accepted
time: 4ms
memory: 5680kb
input:
3
output:
NO
result:
ok Everything ok
Test #6:
score: 0
Accepted
time: 0ms
memory: 5732kb
input:
5
output:
NO
result:
ok Everything ok
Test #7:
score: 0
Accepted
time: 4ms
memory: 5872kb
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: 20ms
memory: 79148kb
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: 25ms
memory: 79180kb
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: 23ms
memory: 79192kb
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: 27ms
memory: 79188kb
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: 36ms
memory: 79428kb
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: 15ms
memory: 79460kb
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: 24ms
memory: 79184kb
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: 20ms
memory: 79460kb
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: 24ms
memory: 79208kb
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: 79180kb
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: 29ms
memory: 79192kb
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: 20ms
memory: 79188kb
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: 32ms
memory: 79212kb
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: 41ms
memory: 79156kb
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: 31ms
memory: 79208kb
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: 29ms
memory: 79264kb
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: 19ms
memory: 79152kb
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: 25ms
memory: 79208kb
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: 28ms
memory: 79192kb
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: -100
Wrong Answer
time: 23ms
memory: 79340kb
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:
wrong answer Not asymmetric