QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#116461#5434. Binary SubstringsLYC_musicTL 56ms17908kbC++142.0kb2023-06-29 10:18:532023-06-29 10:18:55

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-29 10:18:55]
  • 评测
  • 测评结果:TL
  • 用时:56ms
  • 内存:17908kb
  • [2023-06-29 10:18:53]
  • 提交

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

output:


result: