QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#403039#5434. Binary Substringswangif424RE 5ms20176kbC++234.1kb2024-05-01 19:46:452024-05-01 19:47:03

Judging History

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

  • [2024-05-01 19:47:03]
  • 评测
  • 测评结果:RE
  • 用时:5ms
  • 内存:20176kb
  • [2024-05-01 19:46:45]
  • 提交

answer

#include <bits/stdc++.h>
#define R(x) x = read()
#define ENDL push('\n');
#define SPACE push(' ');
//#define int long long
using namespace std;
char pbuf[1<<20], *pp=pbuf;
inline void push(const char &c) {
	if(pp - pbuf == 1<<20)fwrite(pbuf, 1, 1<<20, stdout),pp = pbuf;
	*pp++ = c;
}
class io {public:~io() {fwrite(pbuf, 1, pp - pbuf, stdout);}} _;
inline void write(int x) {
	if (x<0)x=-x,push('-');
	int sta[35],top=0;
	do {
		sta[top++]=x%10,x/=10;
	} while (x);
	while(top)push(sta[--top]^'0');
}
//#ifndef LOCAL
//	char buf[1<<23],*p1=buf,*p2=buf;
//	#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
//#endif
inline int read() {
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
    return x*f;
}
int n,k;
constexpr int N=1<<20;
struct edge{
	int to,nxt=-1;
}v[N];
int len,fir[N];
void add(int x,int y){
	++len;
	v[len].to=y;
	v[len].nxt=fir[x];
	fir[x]=len;
}
int vis[N];
int ola[N],siz;
int mhd[N],tot,nxt[N],pre[N];
void dfo(int u){
//	cout << u << '\n';
	for(int i=fir[u];i!=-1;i=v[i].nxt){
//		cerr << vis[i] << '|';
		if(vis[i])continue;
		vis[i]=1;
		dfo(v[i].to);
	}
	ola[++siz]=u;
}
int num;
int dfn[N],low[N],cnt,ks,id[N],s[N],sy[N];
stack<int> st;
void dfs(int u){
//	cerr << '{' << u;
	low[u]=dfn[u]=++cnt;
	vis[u]=1;
	st.push(u);
	for(int i=fir[u];i;i=v[i].nxt){
		if(vis[v[i].to])low[u]=min(dfn[v[i].to],low[u]);
		else if(!dfn[v[i].to]){
			dfs(v[i].to);
			low[u]=min(low[u],low[v[i].to]);
		}
	}
	if(dfn[u]==low[u]){
		++ks;
		while(st.top()^u){
			id[st.top()]=ks;
			vis[st.top()]=0;
			st.pop();
		}
		id[u]=ks;
		sy[id[u]]=u;
		st.pop();
		vis[u]=0;
	}
}
int chs[N]; 
int to[N];
signed main(){
//	freopen("1.txt","w",stdout);
	memset(fir,-1,sizeof(fir));
	R(n);
	if(n<5){
		switch(n){
			case 1:{
				push('1');
				break;
			}
			case 2:{
				write(10);
				break;
			}
			case 3:{
				write(101);
				break;
			}
			case 4:{
				write(1001);
				break;
			}
		}
		return 0;
	}
	int l=1,rr=n;
	while(l<rr){
		int mid=(l+rr+1)>>1;
		if(mid<=1.0*log2(n*1.0+1-mid))l=mid;
		else rr=mid-1;
	}
	k=l-1;
	for(int i=0;i<(1<<k);i++){
		add(i,(i<<1)&((1<<k)-1));
		add(i,((i<<1)&((1<<k)-1))+1);
	}
	dfo(0);
//	return 0;
	for(int i=1;i<=siz/2;i++)swap(ola[i],ola[siz-i+1]);
	tot=(1<<(k+1));
	for(int i=1;i<=tot;i++)mhd[i]=(ola[i]<<1)|ola[i+1];
	
	memset(vis, 0,sizeof(vis));
	memset(fir,-1,sizeof(fir));
	for(int i=1;i<=len;i++)v[i].nxt=-1;
	
	for(int i=1;i<=tot;i++){
		nxt[mhd[i]]=mhd[i==tot?1:i+1];
	}
	k++;
//	cerr << "||" << nxt[7];
	for(int i=0;i<(1<<k);i++){
//		cerr << "{" << i << ' ' <<((i<<1)&((1<<k)-1)) << ' ' <<nxt[i] << '\n';
		if(((i<<1)&((1<<k)-1))==nxt[i]){
			add(i,((i<<1)&((1<<k)-1))+1);
			to[i]=((i<<1)&((1<<k)-1))+1;
		}else{
			add(i,(i<<1)&((1<<k)-1));
			to[i]=((i<<1)&((1<<k)-1));
		}
//		cerr << i << ' ' << to[i] << '\n';
	}
	num=n-(tot+k-1);
	for(int i=1;i<=tot;i++)if(!dfn[mhd[i]])dfs(mhd[i]);
	for(int i=1;i<=tot;i++)s[id[mhd[i]]]++;
//	for(int i=1;i<=tot;i++)cerr << id[mhd[i]] << ' ';
//	cerr<<'\n' << num;
	int r,st,th;
	for(int i=1;i<=ks;i++){
		if(num>=s[i]&&chs[i]==0){
			num-=s[i];
			chs[i]=1;
//			cerr << ':' << sy[i] << ' ' << i << '\n';
		}
		else{
			chs[i]=2;
			th=i;
			st=nxt[sy[th]];
			r=i;
			break;
		}
	}
//	for(int i=1;i<=ks;i++)cerr << chs[i];
//	cerr<<'\n';
	int b=st>>1,c=0;
	for(int i=1;i<k;i++){
		c=(c<<1)|(b&1);
		b>>=1;
	}
	for(int i=1;i<k;i++){
		write(c&1);
		c>>=1;
	}
	for(int i=st;i!=sy[th];i=nxt[i]){
//		cerr << i <<'\n';
		write(i&1);//cerr<<(i&1);
		if(chs[id[i]]==1){
//			cerr << id[i] << ' ' << chs[id[i]] << '\n';
//			push('(');
			chs[id[i]]=0;
//			cerr << sy[id[i]] << '\n';
//			cerr << ;
			for(int u=to[i],tep=s[id[i]];tep>0;tep--,u=to[u]){
				write(u&1);
//				cerr << u << '\n';
			}
//			push(')');
		}
	}
//	cerr << sy[th] << ' ' << nxt[sy[th]];
	write(sy[th]&1);
//	push(' ');
	for(int u=to[sy[th]];num>0;num--,u=to[u]){
		write(u&1);
	}
	return 0;
}


詳細信息

Test #1:

score: 100
Accepted
time: 5ms
memory: 15824kb

input:

2

output:

10

result:

ok meet maximum 3

Test #2:

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

input:

5

output:

01100

result:

ok meet maximum 12

Test #3:

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

input:

1

output:

1

result:

ok meet maximum 1

Test #4:

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

input:

3

output:

101

result:

ok meet maximum 5

Test #5:

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

input:

4

output:

1001

result:

ok meet maximum 8

Test #6:

score: 0
Accepted
time: 4ms
memory: 20068kb

input:

6

output:

110001

result:

ok meet maximum 16

Test #7:

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

input:

7

output:

1100010

result:

ok meet maximum 21

Test #8:

score: 0
Accepted
time: 3ms
memory: 20040kb

input:

8

output:

10100011

result:

ok meet maximum 27

Test #9:

score: -100
Runtime Error

input:

9

output:


result: