QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#116461 | #5434. Binary Substrings | LYC_music | TL | 56ms | 17908kb | C++14 | 2.0kb | 2023-06-29 10:18:53 | 2023-06-29 10:18:55 |
Judging History
answer
#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define int ll
#define N 1100005
using namespace std;
int n,p[N],vis[N],nxt[N],fa[N];
mt19937_64 rnd(time(0));
int gf(int x)
{
if (x==fa[x]) return x;
return fa[x]=gf(fa[x]);
}
void merge(int x,int y)
{
x=gf(x),y=gf(y);
if (x==y) return;
fa[y]=x;
}
void BellaKira()
{
cin>>n;
if (n==1)
{
cout<<1<<'\n';
return;
}
if (n==2)
{
cout<<"01"<<'\n';
return;
}
int m=0;
for (int i=1;i<=20;i++)
if ((1<<i)>=n-i+1)
{
m=i;
break;
}
while (1)
{
for (int i=0;i<(1<<m);i++)
fa[i]=i,p[i]=i;
shuffle(p,p+(1<<m),rnd);
for (int i=0;i<(1<<m);i++)
{
int o=((i>>(m-1))&1);
nxt[i]=(i*2+o)%(1<<m);
merge(i,nxt[i]);
// cout<<"!!"<<i<<" "<<nxt[i]<<'\n';
}
for (int i=0;i<(1<<m);i++)
{
int u=p[i];
int o=((u>>(m-1))&1);
int v=(u*2+o)%(1<<m);
if (nxt[u]==v)
{
v^=1;
// cout<<"??"<<u<<" "<<v<<" "<<gf(u)<<" "<<gf(v)<<'\n';
if (gf(u)!=gf(v))
{
// cout<<"??"<<u<<" "<<v<<'\n';
merge(u,v);
swap(nxt[u],nxt[u^(1<<(m-1))]);
}
}
}
int now=rnd()%(1<<m);
string ans="";
for (int j=m-1;j>=0;j--) ans+=char((now>>j)%2+'0');
// cout<<"!!"<<now<<endl;
for (int j=1;j<=n-m;j++)
{
now=nxt[now];
// cout<<"!!"<<now<<endl;
ans+=char(now%2+'0');
}
bool bl=1;
if (m>1)
{
m--;
memset(vis,0,sizeof(vis));
for (int i=0;i+m-1<ans.size();i++)
{
int x=0;
for (int j=i;j<i+m;j++) x=x*2+ans[j]-'0';
vis[x]=1;
}
// cout<<"???"<<m<<endl;
// for (int i=0;i<(1<<m);i++) cout<<i<<" "<<vis[i]<<'\n';
for (int i=0;i<(1<<m);i++) bl&=vis[i];
m++;
}
if (bl)
{
cout<<ans<<'\n';
return;
}
}
}
signed main()
{
IOS;
cin.tie(0);
int T=1;
while (T--)
{
BellaKira();
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3556kb
input:
2
output:
01
result:
ok meet maximum 3
Test #2:
score: 0
Accepted
time: 1ms
memory: 17908kb
input:
5
output:
00110
result:
ok meet maximum 12
Test #3:
score: 0
Accepted
time: 1ms
memory: 3488kb
input:
1
output:
1
result:
ok meet maximum 1
Test #4:
score: 0
Accepted
time: 1ms
memory: 15800kb
input:
3
output:
001
result:
ok meet maximum 5
Test #5:
score: 0
Accepted
time: 2ms
memory: 17908kb
input:
4
output:
0011
result:
ok meet maximum 8
Test #6:
score: 0
Accepted
time: 4ms
memory: 15776kb
input:
6
output:
100011
result:
ok meet maximum 16
Test #7:
score: 0
Accepted
time: 2ms
memory: 15748kb
input:
7
output:
0100011
result:
ok meet maximum 21
Test #8:
score: 0
Accepted
time: 1ms
memory: 15824kb
input:
8
output:
01000111
result:
ok meet maximum 27
Test #9:
score: 0
Accepted
time: 3ms
memory: 15880kb
input:
9
output:
010001110
result:
ok meet maximum 34
Test #10:
score: 0
Accepted
time: 0ms
memory: 17868kb
input:
10
output:
0100011101
result:
ok meet maximum 42
Test #11:
score: 0
Accepted
time: 56ms
memory: 15744kb
input:
11
output:
00010111100
result:
ok meet maximum 50
Test #12:
score: 0
Accepted
time: 4ms
memory: 15824kb
input:
12
output:
100001011110
result:
ok meet maximum 59
Test #13:
score: -100
Time Limit Exceeded
input:
200000