QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#300968 | #5434. Binary Substrings | OAleksa | WA | 21ms | 24340kb | C++14 | 1.7kb | 2024-01-09 08:22:42 | 2024-01-09 08:22:43 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
const int N = 2e5 + 69;
vector<int> g[N];
int vis[N], id[N], vis2[N];
int sl[N];
vector<int> ord;
void dfs(int v) {
if (vis[v])
return;
vis[v] = 1;
for (auto u : g[v])
dfs(u);
ord.push_back(v);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
int k = 0;
while ((1 << (k + 1)) + k <= n)
++k;
if (n == 1) {
cout << "0";
return 0;
}
else if (n == 2) {
cout << "01";
return 0;
}
for (int i = 0;i < (1 << k);i++) {
int x = (i * 2) % (1 << k);
g[i].push_back(x);
g[i].push_back(x + 1);
}
dfs(0);
reverse(ord.begin(), ord.end());
int sz = ord.size();
if (n == (1 << k) + k - 1) {
for (int i = 0;i < k - 1;i++)
cout << 0;
for (auto u : ord)
cout << (u & 1);
return 0;
}
for (int i = 0;i < sz;i++) {
ord[i] *= 2;
if (i < sz - 1)
ord[i] |= (ord[i + 1] & 1);
vis2[ord[i]] = 1; //postoji
}
for (int i = 0;i < sz;i++)
sl[ord[i]] = ord[(i + 1) % sz];
for (int i = 0;i < (1 << (k + 1));i++) {
if (vis2[i])
continue;
sl[i] = sl[i ^ (1 << k)] ^ 1;
}
int t = sz;
for (int mask = 0;mask < (1 << (k + 1));mask++) {
if (vis2[mask])
continue;
int j = mask;
while (!vis2[j]) {
t++;
vis2[j] = 1;
j = sl[j];
}
swap(sl[mask], sl[mask ^ (1 << k)]);
if (t + k >= n) {
int x = sl[mask];
for (int i = k;i > 0;i--) {
cout << (x >> i & 1);
}
for (int i = 0;i < n - k;i++) {
cout << (x & 1);
x = sl[x];
}
return 0;
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 9632kb
input:
2
output:
01
result:
ok meet maximum 3
Test #2:
score: 0
Accepted
time: 0ms
memory: 9508kb
input:
5
output:
00110
result:
ok meet maximum 12
Test #3:
score: 0
Accepted
time: 1ms
memory: 8704kb
input:
1
output:
0
result:
ok meet maximum 1
Test #4:
score: 0
Accepted
time: 1ms
memory: 8916kb
input:
3
output:
010
result:
ok meet maximum 5
Test #5:
score: 0
Accepted
time: 0ms
memory: 8644kb
input:
4
output:
0100
result:
ok meet maximum 8
Test #6:
score: 0
Accepted
time: 1ms
memory: 8616kb
input:
6
output:
001100
result:
ok meet maximum 16
Test #7:
score: 0
Accepted
time: 0ms
memory: 10316kb
input:
7
output:
0011000
result:
ok meet maximum 21
Test #8:
score: 0
Accepted
time: 0ms
memory: 11276kb
input:
8
output:
10001101
result:
ok meet maximum 27
Test #9:
score: 0
Accepted
time: 2ms
memory: 11716kb
input:
9
output:
100011010
result:
ok meet maximum 34
Test #10:
score: 0
Accepted
time: 1ms
memory: 9096kb
input:
10
output:
0001011100
result:
ok meet maximum 42
Test #11:
score: 0
Accepted
time: 2ms
memory: 11072kb
input:
11
output:
00010111000
result:
ok meet maximum 50
Test #12:
score: 0
Accepted
time: 0ms
memory: 12128kb
input:
12
output:
000101110000
result:
ok meet maximum 59
Test #13:
score: -100
Wrong Answer
time: 21ms
memory: 24340kb
input:
200000
output:
101111111001110011111111101000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
wrong answer not meet maximum 5599502 < 19996962278