QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#398383#5434. Binary SubstringsnKessiWA 6ms13236kbC++142.7kb2024-04-25 11:20:102024-04-25 11:20:11

Judging History

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

  • [2024-04-25 11:20:11]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:13236kb
  • [2024-04-25 11:20:10]
  • 提交

answer

/*
世界の果てさえ
【世界的尽头在何处】
仆らは知らない
【我们也无从知晓】
*/
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <random>
#include <ctime>
#define pr pair <int, int>
#define mr make_pair
#define LL long long
using namespace std;
const int MAXN = 2e5 + 5;
int n, mx = 1, ext, lim, now[MAXN], p[MAXN], tot, q[MAXN], F[MAXN], out[MAXN];
int ans[MAXN], res;
bool vis[MAXN][2], usd[MAXN];
void read(int &x) {
	x = 0; bool f = 1; char C = getchar();
	for(; C < '0' || C > '9'; C = getchar()) if(C == '-') f = 0;
	for(; C >= '0' && C <= '9'; C = getchar()) x = (x << 1) + (x << 3) + (C ^ 48);
	x = (f ? x : -x);
}
void dfs0(int x) {
	for(int &i = now[x]; i <= 1; i ++) {
		if(vis[x][i]) continue;
		vis[x][i] = 1; dfs0((x << 1 | i) & lim);
	}
	p[++ tot] = x;
}
int main() {
	read(n); int id = 0;
	if(n == 1) {
		printf("0"); return 0;
	}
	if(n == 2) {
		printf("01"); return 0;
	}
	if(n == 3) {
		printf("011"); return 0;
	}
	while((1 << (mx + 1)) <= n - (mx + 1) + 1) mx ++;
	ext = n - mx - (1 << mx); lim = (1 << (mx - 1)) - 1; dfs0(0);
//	printf("?%d %d?", mx, lim);
//	printf("|%d|", tot);
	reverse(p + 1, p + 1 + tot);
	for(int i = 1; i <= tot - 1; i ++) {
		q[i] = (p[i] << 1 | (p[i + 1] & 1));
	}
//	for(int i = 1; i <= tot - 1; i ++) printf("*%d*", q[i]);
	q[tot] = q[1]; lim ++; lim <<= 1; lim --;
	for(int i = 1; i <= tot - 1; i ++) {
		if(q[i + 1] & 1) {
			F[i] = 1; out[q[i]] = (q[i] << 1) & lim;
		}
		else F[i] = 0, out[q[i]] = (q[i] << 1 | 1) & lim;
	}
	tot --; int ls = ext;
//	printf("|%d %d|", tot, ext);
	for(int i = 1; i <= tot; i ++) {
		if(usd[q[i]]) continue;
		int t = q[i]; int x = out[t], cnt = 1; usd[t] = 1;
		while(x ^ t) usd[x] = 1, x = out[x], cnt ++;
		if(ext > cnt) ext -= cnt;
		else {
			id = i; break;
		}
	}
	ext = ls;
	for(int i = mx - 1; i >= 0; i --) ans[++ res] = q[id + 1] >> i & 1;
	for(int i = id + 2; i <= tot; i ++) ans[++ res] = (q[i] & 1);
	memset(usd, 0, sizeof(usd));// printf("?%d?", id);
//	for(int i = 1; i <= res; i ++) printf("?%d?", ans[i]);
	for(int i = (id == tot ? 2 : 1); i <= id; i ++) {
		ans[++ res] = (q[i] & 1);
		if(usd[q[i]]) continue;
		int t = q[i]; int x = out[t], cnt = 1; usd[t] = 1;
		while(x ^ t) usd[x] = 1, x = out[x], cnt ++;
		if(ext > cnt) {
			x = out[t];
			while(x ^ t) ans[++ res] = (x & 1), x = out[x];
			ext -= cnt; ans[++ res] = (t & 1);
		}
		else if(ext >= 0) {
			x = out[x];
			for(int j = 1; j <= ext; j ++, x = out[x]) ans[++ res] = (x & 1);
		}
	}
	if(ext >= 0) ans[++ res] = (q[id + 1] & 1);
	for(int i = 1; i <= res; i ++) putchar(ans[i] + '0');
	return 0;
}

詳細信息

Test #1:

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

input:

2

output:

01

result:

ok meet maximum 3

Test #2:

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

input:

5

output:

01100

result:

ok meet maximum 12

Test #3:

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

input:

1

output:

0

result:

ok meet maximum 1

Test #4:

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

input:

3

output:

011

result:

ok meet maximum 5

Test #5:

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

input:

4

output:

0010

result:

ok meet maximum 8

Test #6:

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

input:

6

output:

011001

result:

ok meet maximum 16

Test #7:

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

input:

7

output:

0110001

result:

ok meet maximum 21

Test #8:

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

input:

8

output:

11000101

result:

ok meet maximum 27

Test #9:

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

input:

9

output:

110001011

result:

ok meet maximum 34

Test #10:

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

input:

10

output:

0010111000

result:

ok meet maximum 42

Test #11:

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

input:

11

output:

00101110001

result:

ok meet maximum 50

Test #12:

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

input:

12

output:

001011100001

result:

ok meet maximum 59

Test #13:

score: 0
Accepted
time: 6ms
memory: 13236kb

input:

200000

output:

000000011000000000000001010000000000000011100000000000001001000000000000010110000000000000110100000000000001111000000000000100010000000000001001100000000000010101000000000000101110000000000001100100000000000011011000000000000111010000000000001111100000000000100001000000000001000110000000000010010100...

result:

ok meet maximum 19996962278

Test #14:

score: -100
Wrong Answer
time: 0ms
memory: 3580kb

input:

24

output:

001001101011110000011100

result:

wrong answer not meet maximum 239 < 240