QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#398956#5434. Binary SubstringsLCX756WA 2ms10048kbC++142.4kb2024-04-25 20:20:302024-04-25 20:20:31

Judging History

你现在查看的是最新测评结果

  • [2024-04-25 20:20:31]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:10048kb
  • [2024-04-25 20:20:30]
  • 提交

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