QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#398022#5434. Binary SubstringsqwqUwU_WA 18ms14364kbC++171.6kb2024-04-24 21:16:402024-04-24 21:16:41

Judging History

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

  • [2024-04-24 21:16:41]
  • 评测
  • 测评结果:WA
  • 用时:18ms
  • 内存:14364kb
  • [2024-04-24 21:16:40]
  • 提交

answer

// clang-format off
#include<bits/stdc++.h>
#define pb push_back
#define P make_pair
#define fi first
#define se second
#define bit(s,i) (((s)>>(i))&1)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
typedef long long ll; 
inline ll read(){
	ll x=0,f=1,c=getchar();
	while(c<'0'||c>'9')f=(c=='-'?-1:1),c=getchar();
	while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
const int N=2e5+3;
// clang-format on
int n,m,a[N];
bool vis[N][2];
int ans[N<<1];
int D,top;
inline void dfs(int u){
	if(!vis[u][0]){
		vis[u][0]=1;
		dfs((u<<1|0)&((1<<D)-1));
		a[++top]=0;
	}
	if(!vis[u][1]){
		vis[u][1]=1;
		dfs((u<<1|1)&((1<<D)-1));
		a[++top]=1;
	}
}
vector<int>vec[N];
vector<int>ed;
int main() {
    //freopen("data.in", "r", stdin);
    // freopen(".in","r",stdin);
    // freopen("myans.out","w",stdout);
	n=read();
	if(n==1){puts("1");return 0;}
	if(n==2){puts("01");return 0;}
	for(;(1<<m)+m-1<=n;++m);--m;
	int tot=0;
	top=0,D=m-1,dfs(0);
	per(i,top,1)ans[++tot]=a[i];
	memset(vis,0,sizeof vis);
	rep(i,1,tot){
		int u=0;
		rep(j,i-m+1,i)u=u<<1|(j>=1?ans[j]:0);
		vis[u][ans[i+1]]=1;
	}
	D=m;
	int cnt=tot;
	rep(i,1,INT_MAX){
		int u=0;
		rep(j,i-m+1,i)u=u<<1|(j>=1?ans[j]:0);
		top=0,dfs(u);
		per(j,top,1)vec[i].pb(a[j]);
		if((cnt+=top)>=n-m){
			per(j,m-1,0)ed.pb(bit(ans[i],j));
			rep(j,i+1,tot)ed.pb(ans[j]);
			rep(j,1,i){
				ed.pb(ans[j]);
				for(auto x:vec[j])ed.pb(x);
			}
			ed.resize(n);
			break;
		}
	}
	for(auto x:ed)printf("%d",x);
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 8384kb

input:

2

output:

01

result:

ok meet maximum 3

Test #2:

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

input:

5

output:

00110

result:

ok meet maximum 12

Test #3:

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

input:

1

output:

1

result:

ok meet maximum 1

Test #4:

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

input:

3

output:

010

result:

ok meet maximum 5

Test #5:

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

input:

4

output:

0100

result:

ok meet maximum 8

Test #6:

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

input:

6

output:

001100

result:

ok meet maximum 16

Test #7:

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

input:

7

output:

0011000

result:

ok meet maximum 21

Test #8:

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

input:

8

output:

01100010

result:

ok meet maximum 27

Test #9:

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

input:

9

output:

011000101

result:

ok meet maximum 34

Test #10:

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

input:

10

output:

0001011100

result:

ok meet maximum 42

Test #11:

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

input:

11

output:

00010111000

result:

ok meet maximum 50

Test #12:

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

input:

12

output:

000101110000

result:

ok meet maximum 59

Test #13:

score: -100
Wrong Answer
time: 18ms
memory: 14364kb

input:

200000

output:

000000000000000000000000101000000000000001110000000000000100100000000000001011000000000000011010000000000000111100000000000010001000000000000100110000000000001010100000000000010111000000000000110010000000000001101100000000000011101000000000000111110000000000010000100000000000100011000000000001001010...

result:

wrong answer not meet maximum 19996962251 < 19996962278