QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#437671#5434. Binary Substringschenxinyang2006RE 2ms16248kbC++203.7kb2024-06-09 14:54:292024-06-09 14:54:30

Judging History

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

  • [2024-06-09 14:54:30]
  • 评测
  • 测评结果:RE
  • 用时:2ms
  • 内存:16248kb
  • [2024-06-09 14:54:29]
  • 提交

answer

#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
	if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
	if(x > y) x = y;
}

inline int popcnt(int x){
	return __builtin_popcount(x);
}

inline int ctz(int x){
	return __builtin_ctz(x);
}


/*ll power(ll p,int k = mod - 2){
	ll ans = 1;
	while(k){
		if(k % 2 == 1) ans = ans * p % mod;
		p = p * p % mod;
		k /= 2;	
	}
	return ans;
}*/
int n,k;

vector <pii> G[1 << 19];
int cnt,cur[1 << 19],buc[1 << 19];
void add(int u,int v){
//	printf("add %d->%d\n",u,v);
	++cnt;
	G[u].eb(mkp(v,cnt));
	G[v].eb(mkp(u,cnt));
}

void addd(int u,int v){
	++cnt;
	G[u].eb(mkp(v,cnt));
}

vector <int> ans;
void dfs(int u){
	for(int i = cur[u];i < SZ(G[u]);i = cur[u]){
		cur[u] = i + 1;
		int v = G[u][i].first;
		if(buc[G[u][i].second]) continue;
		buc[G[u][i].second] = 1;
		dfs(v);
		ans.eb(v & 1);
	}
}
int nxt[1 << 19][2],val[1 << 19],idx[1 << 19],vis[1 << 19],sz[1 << 19];
int cut,remain;
int test(){
	if(remain > sz[cut]) return 0;
	int p = cut;
	while(remain){
		addd(p,nxt[p][1]);
		p = nxt[p][1];
		remain--;
	}
	return 1;
}

int main(){
//	freopen("test.in","r",stdin);
	scanf("%d",&n);
	if(n == 1){
		printf("0\n");
		return 0;
	}
	if(n == 2){
		printf("01\n");
		return 0;
	}
	if(n == 3){
		printf("101\n");
		return 0;
	}
	if(n == 4){
		printf("1001\n");
		return 0;
	}
	while((1 << (k + 1)) + k <= n) k++;

//	printf("k=%d\n",k);
	rep(S,0,(1 << k) - 1) add(S >> 1,S & ((1 << (k - 1)) - 1));
	rep(u,0,(1 << (k - 1)) - 1) if(cur[u] < SZ(G[u])) dfs(u);
/*	printf("semi ans\n");
	for(int p:ans) printf("%d",p);
	printf("\n");*/
	memset(idx,-1,sizeof(idx));
	memset(vis,-1,sizeof(vis));
	rep(i,0,(1 << k) - 1){
		rep(j,0,k - 1) if(ans[(i + j) % (1 << k)]) val[i] |= 1 << (k - 1 - j);
		assert(idx[val[i]] == -1);
		idx[val[i]] = i;
	}
//	rep(i,0,(1 << k) - 1) printf("%d ",val[i]);
//	printf("\n");
	rep(i,0,(1 << k) - 1) nxt[val[i]][0] = val[(i + 1) % (1 << k)];
	rep(S,0,(1 << (k + 1)) - 1){
		int u = S >> 1;
		if((S & ((1 << k) - 1)) != nxt[u][0]) nxt[u][1] = S & ((1 << k) - 1);
	}
	cut = -1;
	rep(u,0,(1 << k) - 1){
		if(vis[u] != -1) continue;
		int p = u;
		while(vis[p] == -1){
			vis[p] = 1;
			p = nxt[p][1];
			sz[u]++;
		}
		if(cut == -1 || sz[cut] < sz[u]) cut = u;
	}
/*	rep(u,0,(1 << k) - 1) printf("%d ",nxt[u][0]);
	printf("\n");
	rep(u,0,(1 << k) - 1) printf("%d ",nxt[u][1]);
	printf("\n");	*/
//	return 0;
	rep(u,0,(1 << k) - 1) G[u].clear();
	memset(buc,0,sizeof(buc));
	memset(cur,0,sizeof(cur));
	memset(vis,-1,sizeof(vis));
	cnt = 0;
	remain = n - k - (1 << k) + 1;
/*	printf("remain=%d cut=%d\n",remain,cut);
	rep(u,0,(1 << k) - 1) printf("%d ",sz[u]);
	printf("\n");*/
	int ovo = 0;
	rep(u,0,(1 << k) - 1){
		if(!sz[u] || u == cut) continue;
		ovo |= test();
		if(ovo) break;
		int p = u;
		while(vis[p] == -1){
			addd(p,nxt[p][1]);
			vis[p] = 1;
			p = nxt[p][1];
			remain--;
		}
	}
	if(!ovo) test();
	rep(u,0,(1 << k) - 1) if(u != cut) addd(u,nxt[u][0]);

	ans.clear();
	dfs(nxt[cut][0]);
	per(i,k - 1,0) printf("%d",nxt[cut][0] >> i & 1);
	reverse(ans.begin(),ans.end());
	for(int p:ans) printf("%d",p);
	printf("\n");
	//接下来视为长度为 k 的串之间的 transfer
	return 0; 
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3808kb

input:

2

output:

01

result:

ok meet maximum 3

Test #2:

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

input:

5

output:

11001

result:

ok meet maximum 12

Test #3:

score: 0
Accepted
time: 1ms
memory: 3904kb

input:

1

output:

0

result:

ok meet maximum 1

Test #4:

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

input:

3

output:

101

result:

ok meet maximum 5

Test #5:

score: 0
Accepted
time: 1ms
memory: 3724kb

input:

4

output:

1001

result:

ok meet maximum 8

Test #6:

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

input:

6

output:

110010

result:

ok meet maximum 16

Test #7:

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

input:

7

output:

1101001

result:

ok meet maximum 21

Test #8:

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

input:

8

output:

11010001

result:

ok meet maximum 27

Test #9:

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

input:

9

output:

111010001

result:

ok meet maximum 34

Test #10:

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

input:

10

output:

0111010001

result:

ok meet maximum 42

Test #11:

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

input:

11

output:

01110100010

result:

ok meet maximum 50

Test #12:

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

input:

12

output:

011101000101

result:

ok meet maximum 59

Test #13:

score: -100
Runtime Error

input:

200000

output:


result: