QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#563709#5434. Binary SubstringsWuyanruWA 2ms9048kbC++143.7kb2024-09-14 15:19:292024-09-14 15:19:33

Judging History

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

  • [2024-09-14 15:19:33]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:9048kb
  • [2024-09-14 15:19:29]
  • 提交

answer

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline ll lread()
{
    ll s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
mt19937 _rand(time(0)^clock());
int fa[300001],siz[300001];
bool go[300001];
int to[300001][2];
char s[300001];
int n,k,c,cnt;
void dfs(int num,int k)
{
    int lim=(1<<k)-1;
    int fir=_rand()%2;
    if(!to[num][fir])
    {
        to[num][fir]=1;
        dfs((num<<1|fir)&lim,k);
        s[c--]=fir+'0';
    }
    fir^=1;
    if(!to[num][fir])
    {
        to[num][fir]=1;
        dfs((num<<1|fir)&lim,k);
        s[c--]=fir+'0';
    }
}
inline int run(int p)
{
    c=(2<<p)+p;
    memset(s,'0',sizeof(s));s[c+1]=0;
    memset(to,0,sizeof(to));
    dfs(0,p);
    // printf("%s\n",s+1);

    memset(to,0,sizeof(to));
    int lim=(1<<(p+1))-1,lst=0,now=0;
    for(int i=1;i<=(2<<p)+p;i++)
    {
        now=((now<<1)+s[i]-'0')&lim;
        if(i>k) to[lst][s[i]-'0']=1;
        lst=now;
        // printf("i=%d now=%d\n",i,now);
    }
    // for(int i=0;i<=lim;i++) printf("%d : %d %d\n",i,to[i][0],to[i][1]);
    return lst;
}
inline void run(int &num,int now)
{
    int mem=now;
    do
    {
        for(int i=0;i<2;i++) if(!to[now][i])
        {
            s[num++]=i+'0';
            now=(now<<1|i)&((1<<k)-1);
        }
    }while(now!=mem);
}
void output(int num,int now)
{
    // printf("output %d %d\n",num,now);
    if(num==n+1)
    {
        s[n+1]=0;printf("%s\n",s+1);
        exit(0);
    }
    if(go[now]) run(num,now);
    if(num>n) return ;

    for(int i=0;i<2;i++) if(to[now][i]==1)
    {
        to[now][i]=2;s[num]=i+'0';
        output(num+1,(now<<1|i)&((1<<k)-1));
        to[now][i]=1;
    }
    for(int i=0;i<2;i++) if(to[now][i]==0)
    {
        to[now][i]=2;s[num]=i+'0';
        output(num+1,(now<<1|i)&((1<<k)-1));
        to[now][i]=0;
    }
}
inline int find(int num)
{
    if(fa[num]==num) return num;
    return fa[num]=find(fa[num]);
}
inline void merge(int u,int v)
{
    u=find(u),v=find(v);
    if(u==v) return ;
    fa[u]=v,siz[v]+=siz[u];
}
int main()
{
    n=read();
    if(n==1){ printf("0\n");return 0;}
    while(n>=(1<<(k+1))+k) k++;
    // printf("k=%d\n",k);

    while(true)
    {
        cnt++;
        int ma=(1<<k)-1,o=run(k-1);
        for(int i=0;i<=ma;i++) siz[i]=0,fa[i]=i;
        for(int i=0;i<=ma;i++) for(int j=0;j<2;j++) if(!to[i][j])
        {
            int t=(i<<1|j)&ma;
            merge(i,t),siz[find(i)]++;
        }
        int S=0;
        for(int i=0;i<ma;i++) if(find(i)==i) S=max(S,siz[i]);
        if(S!=siz[find(o)]) continue;
        // printf("finish cnt=%d %d %d\n",cnt,S,siz[find(o)]);

        int now=(1<<k)+k-1,need=n-now;
        vc<int>id;for(int i=0;i<=ma;i++) if(find(i)==i&&i!=find(o)) id.push_back(i);
        sort(id.begin(),id.end(),[](int x,int y){ return siz[x]<siz[y];});
        for(int i:id) if(need>=siz[i]) need-=siz[i],go[i]=1;
        // printf("need=%d\n",need);

        for(int i=1;i<=k;i++) s[i]='0';
        // for(int i=0;i<=ma;i++) printf("%d : %d %d\n",i,to[i][0],to[i][1]);
        // for(int i=0;i<=ma;i++) if(find(i)==i) printf("%d : siz=%d\n",i,siz[i]);
        output(k+1,0);
        assert(0);
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 8712kb

input:

2

output:

01

result:

ok meet maximum 3

Test #2:

score: 0
Accepted
time: 0ms
memory: 7480kb

input:

5

output:

00110

result:

ok meet maximum 12

Test #3:

score: 0
Accepted
time: 0ms
memory: 3968kb

input:

1

output:

0

result:

ok meet maximum 1

Test #4:

score: 0
Accepted
time: 1ms
memory: 8304kb

input:

3

output:

010

result:

ok meet maximum 5

Test #5:

score: 0
Accepted
time: 1ms
memory: 8468kb

input:

4

output:

0100

result:

ok meet maximum 8

Test #6:

score: 0
Accepted
time: 1ms
memory: 8116kb

input:

6

output:

001110

result:

ok meet maximum 16

Test #7:

score: 0
Accepted
time: 2ms
memory: 7940kb

input:

7

output:

0011100

result:

ok meet maximum 21

Test #8:

score: 0
Accepted
time: 0ms
memory: 8316kb

input:

8

output:

00111000

result:

ok meet maximum 27

Test #9:

score: 0
Accepted
time: 0ms
memory: 8132kb

input:

9

output:

000111010

result:

ok meet maximum 34

Test #10:

score: 0
Accepted
time: 0ms
memory: 9048kb

input:

10

output:

0001110100

result:

ok meet maximum 42

Test #11:

score: -100
Wrong Answer
time: 0ms
memory: 7396kb

input:

11

output:

00001011110

result:

wrong answer not meet maximum 49 < 50