Submission #1137850

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137850		anmattroi	Unscrambling a Messy Bug (IOI16_messy)	C++17	100 / 100	1 ms	584 KiB

messy

#include <vector>
#include <bits/stdc++.h>
#include "messy.h"

using namespace std;

int p[128];

void element_adder(int l, int r, int n) {
    if (l == r) return;
    int m = (l + r) / 2;
    string s(n, '1');
    for (int i = l; i <= r; i++) s[i] = '0';
    for (int i = l; i <= m; i++) {
        s[i] = '1';
        add_element(s);
        s[i] = '0';
    }
    element_adder(l, m, n);
    element_adder(m+1, r, n);
}

void Restore(int l, int r, int n, vector<int> indices) {
    if (l == r) {
        p[indices[0]] = l;
        return;
    }
    string s(n, '1');
    int sz = indices.size();
    for (int i = 0; i < sz; i++) s[indices[i]] = '0';
    vector<int> L, R;
    for (int i = 0; i < sz; i++) {
        int p = indices[i];
        s[p] = '1';
        if (check_element(s)) L.emplace_back(p);
        else R.emplace_back(p);
        s[p] = '0';
    }

    Restore(l, (l+r)/2, n, L);
    Restore((l+r)/2+1, r, n, R);
}



vector<int> restore_permutation(int n, int w, int r) {
    element_adder(0, n-1, n);
    compile_set();
    vector<int> a(n, 0);
    for (int i = 0; i < n; i++) a[i] = i;
    Restore(0, n-1, n, a);
    vector<int> ans(n);
    for (int i = 0; i < n; i++) ans[i] = p[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: 30 / 30