Submission #1204514

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204514		totoro	Unscrambling a Messy Bug (IOI16_messy)	C++20	70 / 100	1 ms	584 KiB

messy

#include "messy.h"

#include <iostream>
#include <vector>

std::vector<int> restore_permutation(int n, int w, int r) {
    int logn = 0;
    while (1 << logn < n) ++logn;
    int special = logn - 1;  // These are calculated explicitly

    std::string writebuf(n, '0');
    writebuf.assign(n, '1');
    for (int i = 0; i < special; ++i) {
        writebuf[i] = '0';
        add_element(writebuf);
    }

    for (int bit = 0; bit < logn; ++bit) {
        std::string curtemplate(n, '0');
        for (int i = 0; i < bit; ++i) curtemplate[i] = '1';  // set the special bits
        for (int i = special; i < n; ++i) {
            if (i & (1 << (special - bit))) {
                writebuf = curtemplate;
                writebuf[i] = '1';
                add_element(writebuf);
            }
        }
    }

    compile_set();

    std::vector<int> ans(n, -1);
    std::vector<int> inv(n, -1);
    /* Find special bits */
    for (int i = 0; i < special; ++i) {
        std::string curtemplate(n, '1');
        for (int j = 0; j < i; ++j) curtemplate[inv[j]] = '0';  // set the special bits
        for (int j = 0; j < n; ++j) {
            if (ans[j] != -1) continue;
            writebuf = curtemplate;
            writebuf[j] = '0';
            if (check_element(writebuf)) {
                inv[i] = j;
                ans[j] = i;
                break;
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        if (ans[i] != -1) continue;  // it's probably a special bit, so we've already found it
        int j = 0;
        writebuf.assign(n, '0');
        writebuf[i] = '1';
        for (int bit = 0; bit < logn; ++bit) {
            j = (j << 1) + check_element(writebuf);
            if (bit < special) writebuf[inv[bit]] = '1';
        }
        ans[i] = j;
        inv[j] = i;
    }

    return ans;
}

Compilation message (stderr)

messy.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
messy_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• Subtask 1: 20 / 20
• Subtask 2: 18 / 18
• Subtask 3: 11 / 11
• Subtask 4: 21 / 21
• Subtask 5: 0 / 30