QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#398379 | #5434. Binary Substrings | nKessi | WA | 0ms | 3584kb | C++14 | 2.7kb | 2024-04-25 11:19:02 | 2024-04-25 11:19:03 |
Judging History
answer
/*
世界の果てさえ
【世界的尽头在何处】
仆らは知らない
【我们也无从知晓】
*/
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <random>
#include <ctime>
#define pr pair <int, int>
#define mr make_pair
#define LL long long
using namespace std;
const int MAXN = 2e5 + 5;
int n, mx = 1, ext, lim, now[MAXN], p[MAXN], tot, q[MAXN], F[MAXN], out[MAXN];
int ans[MAXN], res;
bool vis[MAXN][2], usd[MAXN];
void read(int &x) {
x = 0; bool f = 1; char C = getchar();
for(; C < '0' || C > '9'; C = getchar()) if(C == '-') f = 0;
for(; C >= '0' && C <= '9'; C = getchar()) x = (x << 1) + (x << 3) + (C ^ 48);
x = (f ? x : -x);
}
void dfs0(int x) {
for(int &i = now[x]; i <= 1; i ++) {
if(vis[x][i]) continue;
vis[x][i] = 1; dfs0((x << 1 | i) & lim);
}
p[++ tot] = x;
}
int main() {
read(n); int id = 0;
if(n == 1) {
printf("0"); return 0;
}
if(n == 2) {
printf("01"); return 0;
}
while((1 << (mx + 1)) <= n - (mx + 1) + 1) mx ++;
ext = n - mx - (1 << mx); lim = (1 << (mx - 1)) - 1; dfs0(0);
// printf("?%d %d?", mx, lim);
// printf("|%d|", tot);
reverse(p + 1, p + 1 + tot);
for(int i = 1; i <= tot - 1; i ++) {
q[i] = (p[i] << 1 | (p[i + 1] & 1));
}
// for(int i = 1; i <= tot - 1; i ++) printf("*%d*", q[i]);
q[tot] = q[1]; lim ++; lim <<= 1; lim --;
for(int i = 1; i <= tot - 1; i ++) {
if(q[i + 1] & 1) {
F[i] = 1; out[q[i]] = (q[i] << 1) & lim;
}
else F[i] = 0, out[q[i]] = (q[i] << 1 | 1) & lim;
}
tot --; int ls = ext;
// printf("|%d %d|", tot, ext);
for(int i = 1; i <= tot; i ++) {
if(usd[q[i]]) continue;
int t = q[i]; int x = out[t], cnt = 1; usd[t] = 1;
while(x ^ t) usd[x] = 1, x = out[x], cnt ++;
if(ext > cnt) ext -= cnt;
else {
id = i; break;
}
}
ext = ls;
for(int i = mx - 1; i >= 0; i --) ans[++ res] = q[id + 1] >> i & 1;
for(int i = id + 2; i <= tot; i ++) ans[++ res] = (q[i] & 1);
memset(usd, 0, sizeof(usd));// printf("?%d?", id);
// for(int i = 1; i <= res; i ++) printf("?%d?", ans[i]);
for(int i = (id == tot ? 2 : 1); i <= id; i ++) {
ans[++ res] = (q[i] & 1);
if(usd[q[i]]) continue;
int t = q[i]; int x = out[t], cnt = 1; usd[t] = 1;
while(x ^ t) usd[x] = 1, x = out[x], cnt ++;
if(ext > cnt) {
x = out[t];
while(x ^ t) ans[++ res] = (x & 1), x = out[x];
ext -= cnt; ans[++ res] = (t & 1);
}
else if(ext >= 0) {
x = out[x];
for(int j = 1; j <= ext; j ++, x = out[x]) ans[++ res] = (x & 1);
}
}
if(ext >= 0) ans[++ res] = (q[id + 1] & 1);
for(int i = 1; i <= res; i ++) putchar(ans[i] + '0');
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 1392kb
input:
2
output:
01
result:
ok meet maximum 3
Test #2:
score: 0
Accepted
time: 0ms
memory: 1508kb
input:
5
output:
01100
result:
ok meet maximum 12
Test #3:
score: 0
Accepted
time: 0ms
memory: 1376kb
input:
1
output:
0
result:
ok meet maximum 1
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3584kb
input:
3
output:
000
result:
wrong answer not meet maximum 3 < 5