QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#398222 | #5434. Binary Substrings | cqbzly | WA | 7ms | 10808kb | C++14 | 2.3kb | 2024-04-25 09:08:22 | 2024-04-25 09:08:23 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define db double
#define fi first
#define se second
#define vi vector<int>
#define inf 0x3f3f3f3f
using namespace std;
const int N=4e5+5;
int n,K,p[N],lim,sz,rest,cnt,s,to[N];
bool vs[N],vs0[N],vs1[N],vs2[N];
bool dfs(int u){
vs[u]=1,p[sz++]=u;
if(sz==(1<<K)&&u==(1<<K-1))return 1;
if(!vs[(u<<1)&lim]&&dfs((u<<1)&lim))return 1;
if(!vs[(u<<1|1)&lim]&&dfs((u<<1|1)&lim))return 1;
sz--,vs[u]=0;return 0;
}
int id(int x,int y){
if(x>>K-1&1)return y|(1<<K);
return y;
}
void dfs0(int u,int topf){
int v=(u<<1)&lim;
if(!vs0[id(u,v)]&&id(u,v)!=topf)cnt++,dfs0(v,id(u,v));
}
void dfs1(int u,int topf){
cout<<(u>>K-1&1);
}
vector<int>res;
void opt(){
int sz=res.size();
for(int i=0;i<sz-1;i++){
cout<<(res[i]>>K-1&1);
}
for(int i=K-1;i>=0;i--){
cout<<(res[sz-1]>>i&1);
}
exit(0);
}
signed main(){
// freopen("data.in","r",stdin);
// freopen("own.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n;while((1<<K+1)<=n-K)K++;
lim=(1<<K)-1;
dfs(0);
for(int i=0;i<1<<K;i++){
int x=p[i],y=p[i+1&lim];
vs0[id(x,y)]=1;
}
rest=n-K-(1<<K);
//cout<<rest<<"\n";
if(rest<0){
for(int i=0;i<sz;i++)res.pb(p[i]);
opt();
}
for(int i=0;i<1<<K;i++){
int j=(i<<1)&lim;
if(!vs0[id(i,j)])to[i]=j;
else to[i]=(i<<1|1)&lim;
}
for(int i=0;i<1<<K;i++){
if(!vs1[i]){
cnt=0;
int u=i;
do{
cnt++,u=to[u];
}while(u!=i);
if(rest>=cnt){
rest-=cnt,vs2[i]=1;
}
else if(rest>0){
s=i;
break;
}
}
}
// for(int i=0;i<1<<K;i++){
// cout<<p[i]<<"\n";
// }
int x=0;while(p[x]!=s)x++;
int y=x;
do{
int i=p[y],u=i;
if(vs2[i]){
do{
res.pb(u);
u=to[u];
}while(u!=i);
}
res.pb(i);
y=(y+1)&lim;
}while(y!=x);
int u=p[y];
for(int i=1;i<=rest+1;i++){
res.pb(u);
u=to[u];
}
opt();
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 7724kb
input:
2
output:
01
result:
ok meet maximum 3
Test #2:
score: 0
Accepted
time: 1ms
memory: 5700kb
input:
5
output:
00110
result:
ok meet maximum 12
Test #3:
score: 0
Accepted
time: 1ms
memory: 5688kb
input:
1
output:
0
result:
ok meet maximum 1
Test #4:
score: 0
Accepted
time: 0ms
memory: 5644kb
input:
3
output:
010
result:
ok meet maximum 5
Test #5:
score: 0
Accepted
time: 1ms
memory: 5720kb
input:
4
output:
0010
result:
ok meet maximum 8
Test #6:
score: 0
Accepted
time: 1ms
memory: 7688kb
input:
6
output:
001100
result:
ok meet maximum 16
Test #7:
score: 0
Accepted
time: 1ms
memory: 5668kb
input:
7
output:
0001100
result:
ok meet maximum 21
Test #8:
score: 0
Accepted
time: 0ms
memory: 7740kb
input:
8
output:
01100010
result:
ok meet maximum 27
Test #9:
score: 0
Accepted
time: 1ms
memory: 5712kb
input:
9
output:
000101100
result:
ok meet maximum 34
Test #10:
score: 0
Accepted
time: 1ms
memory: 5636kb
input:
10
output:
0001011100
result:
ok meet maximum 42
Test #11:
score: 0
Accepted
time: 1ms
memory: 7740kb
input:
11
output:
00010111000
result:
ok meet maximum 50
Test #12:
score: 0
Accepted
time: 1ms
memory: 5708kb
input:
12
output:
000010111000
result:
ok meet maximum 59
Test #13:
score: -100
Wrong Answer
time: 7ms
memory: 10808kb
input:
200000
output:
000000000000010000000000000001111111111111111011111111000000000111111101111111110000000011111111011111110000000000111111011111111110000000111111111011111100000000000111110111111111110000001111111111011111000000000000111101111111111110000011111111111011110000000000000111011111111111110000111111111111...
result:
wrong answer not meet maximum 19988894770 < 19996962278