QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#563728 | #5434. Binary Substrings | Wuyanru | WA | 3ms | 8812kb | C++14 | 3.7kb | 2024-09-14 15:29:24 | 2024-09-14 15:29:24 |
Judging History
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(116);
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);
int St=0;
for(int i=1;i<=k;i++) St=(St<<1)|(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,St);
assert(0);
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 8812kb
input:
2
output:
10 10 10 10 10 10 10 10 01 0 : 0 1 1 : 0 0 01
result:
wrong output format Extra information in the output file