QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#398997#5434. Binary SubstringsLCX756RE 7ms20224kbC++142.9kb2024-04-25 20:45:222024-04-25 20:45:27

Judging History

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

  • [2024-04-25 20:45:27]
  • 评测
  • 测评结果:RE
  • 用时:7ms
  • 内存:20224kb
  • [2024-04-25 20:45:22]
  • 提交

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 <= 10) {
        int mx = 0;
        for (int S = 0; S < (1 << n); ++S) {
            int res = 0;
            for (int i = 1; i <= n; ++i) {
                set <int> st;
                for (int l = 0; l + i <= n; ++l)
                    st.insert((S >> l) & ((1 << i) - 1));
                res += st.size();
            }
            if (res > mx) {
                mx = res;
                for (int i = 1; i <= n; ++i)
                    s[i] = ((S >> (i - 1)) & 1) + '0';
            }
        }
        printf("%s\n", s + 1);
        return 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: 10172kb

input:

2

output:

10

result:

ok meet maximum 3

Test #2:

score: 0
Accepted
time: 2ms
memory: 9964kb

input:

5

output:

01100

result:

ok meet maximum 12

Test #3:

score: 0
Accepted
time: 1ms
memory: 8660kb

input:

1

output:

0

result:

ok meet maximum 1

Test #4:

score: 0
Accepted
time: 1ms
memory: 8988kb

input:

3

output:

100

result:

ok meet maximum 5

Test #5:

score: 0
Accepted
time: 1ms
memory: 8720kb

input:

4

output:

0100

result:

ok meet maximum 8

Test #6:

score: 0
Accepted
time: 2ms
memory: 9580kb

input:

6

output:

011000

result:

ok meet maximum 16

Test #7:

score: 0
Accepted
time: 2ms
memory: 9776kb

input:

7

output:

1101000

result:

ok meet maximum 21

Test #8:

score: 0
Accepted
time: 0ms
memory: 9168kb

input:

8

output:

01101000

result:

ok meet maximum 27

Test #9:

score: 0
Accepted
time: 2ms
memory: 9400kb

input:

9

output:

001101000

result:

ok meet maximum 34

Test #10:

score: 0
Accepted
time: 0ms
memory: 9600kb

input:

10

output:

0011101000

result:

ok meet maximum 42

Test #11:

score: 0
Accepted
time: 2ms
memory: 10024kb

input:

11

output:

01011100001

result:

ok meet maximum 50

Test #12:

score: 0
Accepted
time: 1ms
memory: 10128kb

input:

12

output:

010111000011

result:

ok meet maximum 59

Test #13:

score: 0
Accepted
time: 7ms
memory: 20224kb

input:

200000

output:

000000011000000000000001010000000000000011100000000000001001000000000000010110000000000000110100000000000001111000000000000100010000000000001001100000000000010101000000000000101110000000000001100100000000000011011000000000000111010000000000001111100000000000100001000000000001000110000000000010010100...

result:

ok meet maximum 19996962278

Test #14:

score: 0
Accepted
time: 2ms
memory: 10084kb

input:

24

output:

001001101011110000011101

result:

ok meet maximum 240

Test #15:

score: -100
Runtime Error

input:

35

output:


result: