QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#398222#5434. Binary SubstringscqbzlyWA 7ms10808kbC++142.3kb2024-04-25 09:08:222024-04-25 09:08:23

Judging History

你现在查看的是最新测评结果

  • [2024-04-25 09:08:23]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:10808kb
  • [2024-04-25 09:08:22]
  • 提交

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