QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#300965 | #5434. Binary Substrings | OAleksa | WA | 3ms | 9464kb | C++14 | 1.8kb | 2024-01-09 07:53:12 | 2024-01-09 07:53:12 |
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;
}
else if (n == 3) {
cout << "001";
return 0;
}
else if (n == 4) {
cout << "0011";
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;i++)
cout << 0;
for (auto u : ord)
cout << (u & 1);
return 0;
}
for (int i = 0;i < sz;i++) {
ord[i] *= 2;
if (i < n - 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);i++) {
if (vis2[i])
continue;
sl[i] = sl[i ^ (1 << k)] ^ 1;
}
int t = sz + 1;
for (int mask = 0;mask < (1 << k);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: 3ms
memory: 9464kb
input:
2
output:
01
result:
ok meet maximum 3
Test #2:
score: -100
Wrong Answer
time: 2ms
memory: 8364kb
input:
5
output:
000110
result:
wrong answer Token parameter [name=s] equals to "000110", doesn't correspond to pattern "[01]{5}"