QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#398297 | #5434. Binary Substrings | caijianhong | WA | 4ms | 17220kb | C++20 | 2.3kb | 2024-04-25 10:28:12 | 2024-04-25 10:28:14 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define endl "\n"
#define debug(...) void(0)
#endif
typedef long long LL;
int n, k, to[1000010], repr[1000010], bel[1000010], siz[1000010];
vector<int> g[1000010];
vector<int> ans;
void dfs(int u) {
while (!g[u].empty()) {
int v = g[u].back();
g[u].pop_back();
dfs(v);
ans.push_back(v & 1);
}
}
int main() {
#ifndef LOCAL
cin.tie(nullptr)->sync_with_stdio(false);
#endif
cin >> n;
if (n == 1) return cout << "1" << endl, 0;
if (n == 2) return cout << "10" << endl, 0;
while (k + (1 << (k + 1)) <= n) ++k;
int pk1 = 1 << (k - 1), pk2 = pk1 << 2, pk = pk2 >> 1;
for (int i = 0; i < pk1; i++) {
g[i] = {(i << 1 | 1) % pk1, (i << 1) % pk1};
}
dfs(0);
reverse(ans.begin(), ans.end());
ans.insert(ans.begin(), k - 1, 0);
for (int x : ans) cerr << x;
cerr << endl;
memset(to, -1, sizeof to);
int lst = 0;
for (int i = 0, now = 0; i < ans.size(); i++) {
now = (now << 1 | ans[i]) % pk2;
if (i >= k) to[lst] = now;
lst = now;
}
to[lst] = (lst << 1) % pk2;
for (int i = 0; i < pk; i++) {
if (~to[i] && to[i + pk] == -1) to[i + pk] = to[i] ^ 1;
if (~to[i + pk] && to[i] == -1) to[i] = to[i + pk] ^ 1;
}
memset(repr, -1, sizeof repr);
memset(bel, -1, sizeof bel);
for (int i = 0; i < pk2; i++) {
if (~repr[i]) continue;
bel[i] = i;
for (int j = i; repr[j] == -1; j = to[j]) repr[j] = i, siz[i] += 1;
}
for (int i = 0; i < pk; i++) {
if (bel[repr[i]] != bel[repr[i + pk]]) {
int u = repr[i], v = repr[i + pk], flag = false;
if (bel[v] == 0) swap(u, v), flag = true;
if (bel[u] == 0 && siz[u] >= n - k + 1) continue;
bel[v] = u;
siz[u] += siz[v];
swap(to[i], to[i + pk]);
if (bel[u] == 0 && siz[u] >= n - k + 1) {
ans.assign(k - 1, 0);
for (int now = to[i + pk * !flag]; ans.size() < n; now = to[now]) ans.push_back(now & 1);
for (int x : ans) cout << x;
cout << endl;
return 0;
}
}
}
ans.assign(k - 1, 0);
for (int now = 0; ans.size() < n; now = to[now]) ans.push_back(now & 1);
for (int x : ans) cout << x;
cout << endl;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3660kb
input:
2
output:
10
result:
ok meet maximum 3
Test #2:
score: 0
Accepted
time: 0ms
memory: 16832kb
input:
5
output:
00110
result:
ok meet maximum 12
Test #3:
score: 0
Accepted
time: 1ms
memory: 3660kb
input:
1
output:
1
result:
ok meet maximum 1
Test #4:
score: 0
Accepted
time: 0ms
memory: 17152kb
input:
3
output:
011
result:
ok meet maximum 5
Test #5:
score: 0
Accepted
time: 4ms
memory: 16016kb
input:
4
output:
0110
result:
ok meet maximum 8
Test #6:
score: 0
Accepted
time: 0ms
memory: 16760kb
input:
6
output:
001100
result:
ok meet maximum 16
Test #7:
score: -100
Wrong Answer
time: 2ms
memory: 17220kb
input:
7
output:
0100010
result:
wrong answer not meet maximum 19 < 21