Submission #957021

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

messy

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

using namespace std;

typedef long long ll;
typedef tuple<int,int,int> trio;
typedef pair<ll,int> pii;
const int MAXN = 3e5+5;
const int MOD = 1e9+7;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define f first
#define s second

int N, ans[200];

void restore(int l, int r, vector<int> range) {
    if(l == r) {
        ans[l] = range[0];
        return;
    }

    string a;
    vector<bool> in_range(N+1);

    for(int i : range) in_range[i] = 1;

    for(int i = 1; i <= N; i++) a += (char)('0' + !in_range[i]);

    vector<int> range_l, range_r;
    for(int i : range) {
        a[i-1] = '1';
        if(check_element(a)) range_l.pb(i);
        else range_r.pb(i);
        a[i-1] = '0';
    }

    int mid = (l+r)/2;
    restore(l, mid, range_l);
    restore(mid+1, r, range_r);
}

vector<int> restore_permutation(int n, int w, int r) {
    int add = 0;

    for(int S = n; S >= 2; S/=2) {
        for(int i = 1; i <= n; i += S) {
            // range (i, i+S-1)
            string a;

            for(int j = 1; j < i; j++) a += '1';
            for(int j = i; j < i+S; j++) a += '0';
            for(int j = i+S; j <= n; j++) a += '1';

            for(int j = i; j < i + S/2; j++) {
                a[j-1] = '1';
                add_element(a);
                add++;
                a[j-1] = '0';
            }
        }
    }

    compile_set();

    N = n;
    vector<int> aux;
    for(int i = 1; i <= n; i++) aux.pb(i);

    restore(1, n, aux);

    vector<int> answer(n);
    for(int i = 1; i <= n; i++)
        answer[ans[i]-1] = i-1;

    return answer;
}

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