QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#116460#5434. Binary SubstringsLYC_musicWA 0ms3512kbC++142.0kb2023-06-29 10:18:292023-06-29 10:18:32

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:32]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3512kb
  • [2023-06-29 10:18:29]
  • 提交

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();
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3512kb

input:

2

output:

1

result:

wrong answer Token parameter [name=s] equals to "1", doesn't correspond to pattern "[01]{2}"