QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#241572#5434. Binary SubstringsFISHER_WA 5ms20124kbC++141.3kb2023-11-06 11:53:212023-11-06 11:53:22

Judging History

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

  • [2023-11-06 11:53:22]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:20124kb
  • [2023-11-06 11:53:21]
  • 提交

answer

#include <bits/stdc++.h>
#define PB push_back
#define EB emplace_back
using namespace std;
const int maxn = 400000;
vector<int> g[maxn + 5];
int rte[maxn + 5];
int c;
bool vis[2 * maxn + 5];
int S;
void dfs(int u) {
	if (vis[u]) return;
	vis[u] = 1;
	dfs((u << 1) & (S - 1)), dfs(((u << 1) & (S - 1)) | 1);
	rte[++c] = u;
}
int to[2 * maxn + 5];
int main() {
	int n;
	scanf("%d", &n);
	if (n == 1) return puts("0"), 0;
	if (n == 2) return puts("01"), 0;
	int k = 1;
	while ((1 << k) + k - 1 <= n) k++;
	S = 1 << (k - 1);
	dfs(0);
	reverse(rte + 1, rte + c + 1);
	for (int i = 1; i <= c; i++) rte[i] = (rte[i] << 1) | (rte[i + 1] & 1);
	if (n == S + k - 2) {
		for (int i = 1; i < k - 1; i++) putchar('0');
		for (int i = 1; i <= c; i++) putchar('0' + (rte[i] & 1));
		return 0;
	}
	memset(to, -1, sizeof(to));
	for (int i = 1; i <= c; i++) to[rte[i]] = rte[i % c + 1];
	int S2 = 1 << k;
	for (int i = 0; i < S2; i++)
		if (to[i] == -1) to[i] = to[i ^ S] ^ 1;
	memset(vis, 0, sizeof(vis));
	for (int i = 0; i < S2; i++)
		if (!vis[i]) {
			for (int u = i; !vis[u]; u = to[u]) vis[u] = 1, c++;
			swap(to[i], to[i ^ S]);
			if (c + k > n) {
				for (int j = k - 1; ~j; j--) putchar('0' + ((to[i] >> j) & 1));
				for (int j = k + 1, u = to[to[i]]; j <= n; j++, u = to[u]) putchar('0' + (u & 1));
				return 0;
			}
		}
}

详细

Test #1:

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

input:

2

output:

01

result:

ok meet maximum 3

Test #2:

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

input:

5

output:

01100

result:

ok meet maximum 12

Test #3:

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

input:

1

output:

0

result:

ok meet maximum 1

Test #4:

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

input:

3

output:

010

result:

ok meet maximum 5

Test #5:

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

input:

4

output:

0100

result:

ok meet maximum 8

Test #6:

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

input:

6

output:

001100

result:

ok meet maximum 16

Test #7:

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

input:

7

output:

0011000

result:

ok meet maximum 21

Test #8:

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

input:

8

output:

01011000

result:

ok meet maximum 27

Test #9:

score: 0
Accepted
time: 5ms
memory: 17864kb

input:

9

output:

010110001

result:

ok meet maximum 34

Test #10:

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

input:

10

output:

0010111000

result:

ok meet maximum 42

Test #11:

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

input:

11

output:

00010111000

result:

ok meet maximum 50

Test #12:

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

input:

12

output:

000101110000

result:

ok meet maximum 59

Test #13:

score: -100
Wrong Answer
time: 3ms
memory: 20124kb

input:

200000

output:

000000000000000011111111111111110111111110000000001111111011111111100000000111111110111111100000000001111110111111111100000001111111110111111000000000001111101111111111100000011111111110111110000000000001111011111111111100000111111111110111100000000000001110111111111111100001111111111110111000000000...

result:

wrong answer not meet maximum 17649501338 < 19996962278