QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#241572 | #5434. Binary Substrings | FISHER_ | WA | 5ms | 20124kb | C++14 | 1.3kb | 2023-11-06 11:53:21 | 2023-11-06 11:53:22 |
Judging History
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