QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#398956 | #5434. Binary Substrings | LCX756 | WA | 2ms | 10048kb | C++14 | 2.4kb | 2024-04-25 20:20:30 | 2024-04-25 20:20:31 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128_t lll;
typedef double db;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
#define fir first
#define sec second
typedef vector <int> vi;
typedef vector <ll> vl;
#ifdef LCX
#define msg(args...) fprintf(stderr, args)
#else
#define msg(...) void()
#endif
const int maxn = 2e5 + 10;
int n, k;
vi vec;
int vis[maxn][2];
void dfs(int u) {
for (int c = 0; c < 2; ++c)
if (!vis[u][c]) {
vis[u][c] = 1;
int e = (u << 1 | c);
dfs(e & ((1 << (k - 1)) - 1));
vec.push_back(e);
}
}
vi circ[maxn];
void go(int u) {
vi &path = circ[u];
while (1) {
int flg = 1;
for (int c = 0; c < 2 && flg; ++c)
if (!vis[u][c]) {
vis[u][c] = 1;
u = (u << 1 | c) & ((1 << k) - 1);
path.push_back(u);
flg = 0;
}
if (flg) break;
}
}
char s[maxn];
int main() {
scanf("%d", &n);
if (n == 1) return printf("0\n"), 0;
if (n == 2) return printf("01\n"), 0;
while ((1 << k) + k - 1 <= n) ++k;
--k;
dfs(0);
reverse(begin(vec), end(vec));
memset(vis, 0, sizeof vis);
int len = vec.size(), rst = n - (1 << k) - k + 1;
// for (int i = 0; i < len; ++i) msg("%d%c", vec[i], " \n"[i == len - 1]);
for (int i = 0; i < len; ++i)
vis[vec[i]][vec[(i + 1) % len] & 1] = 1;
vi ans;
for (int i = 0; i < len; ++i) {
go(vec[i]);
// msg("@%d\n", rst);
if (rst < (int) circ[vec[i]].size()) {
for (int j = i + 1; j < len; ++j) ans.push_back(vec[j]);
for (int j = 0; j < i; ++j) {
ans.push_back(vec[j]);
for (int u : circ[vec[j]])
ans.push_back(u);
}
ans.push_back(vec[i]);
for (int u : circ[vec[i]]) {
if (!rst) break;
--rst, ans.push_back(u);
}
break;
}
else rst -= circ[vec[i]].size();
}
// msg("ans");
// for (int u : ans) msg(" %d", u);
// msg("\n");
n = 0;
for (int i = k - 1; i > 0; --i)
s[++n] = '0' + ((ans[0] >> i) & 1);
for (int u : ans) s[++n] = '0' + (u & 1);
printf("%s\n", s + 1);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 8540kb
input:
2
output:
01
result:
ok meet maximum 3
Test #2:
score: 0
Accepted
time: 0ms
memory: 10048kb
input:
5
output:
01100
result:
ok meet maximum 12
Test #3:
score: 0
Accepted
time: 0ms
memory: 8372kb
input:
1
output:
0
result:
ok meet maximum 1
Test #4:
score: 0
Accepted
time: 0ms
memory: 9984kb
input:
3
output:
001
result:
ok meet maximum 5
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 9988kb
input:
4
output:
result:
wrong output format Unexpected end of file - token expected