Submission #1161988

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161988		MrDogMeat	Unscrambling a Messy Bug (IOI16_messy)	C++20	100 / 100	2 ms	584 KiB

messy

#include<bits/stdc++.h>
using namespace std;

void add_element(std::string x);
bool check_element(std::string x);
void compile_set();

vector<int> Answer;

void solve(int n, int l, int r, vector<int> subset) {
    cerr << l << " " << r << "\n";
    if(l == r) {
        Answer[subset[0]] = l;
        return;
    }
    string bits(n, '1');
    for(int e : subset) {
        bits[e] = '0';
    }
    vector<int> subsetL, subsetR;
    for(int e : subset) {
        bits[e] = '1';
        if(check_element(bits)) {
            subsetL.push_back(e);
        }
        else {
            subsetR.push_back(e);
        }
        bits[e] = '0';
    }
    int mid = (l + r) / 2;
    solve(n, l, mid, subsetL);
    solve(n, mid + 1, r, subsetR);
}

std::vector<int> restore_permutation(int n, int w, int r) {
    for(int pw2 = 2; pw2 <= n; pw2 *= 2) {
        for(int i = 0; i + pw2 - 1 < n; i += pw2) {
            string bits(n, '1');
            for(int j = 0; j < pw2; j++) {
                bits[i + j] = '0';
            }
            for(int j = 0; j < pw2/2; j++) {
                bits[i + j] = '1';
                add_element(bits);
                cerr << bits << "\n";
                bits[i + j] = '0';
            }
        }
    }
    compile_set();
    vector<int> vcc;
    for(int i = 0; i < n; i++) {
        vcc.push_back(i);
    }
    Answer.resize(n);
    solve(n, 0, n - 1, vcc);
    return Answer;
}

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: 30 / 30