Submission #586184

#	Time	Username	Problem	Language	Result	Execution time	Memory
586184		Do_you_copy	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	3 ms	468 KiB

messy

#include <bits/stdc++.h>
#include <messy.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;

using ll = long long;
using pii = pair <int, int>;

ll min(const ll &a, const ll &b){
    return (a < b) ? a : b;
}

ll max(const ll &a, const ll &b){
    return (a > b) ? a : b;
}

const ll Mod = 1000000007;
const int maxN = 1e5 + 1;
int n;
int a[128];
int hiddenarray[] = {3, 1, 7, 4, 5, 0, 6, 2};
vector <string> v;

struct TNode{
    vector <int> q;
};
/*
void add_element(string s){
    v.pb(s);
}

void compile_set(){
    for (string &t: v){
        string tt = t;
        for (int i = 0; i < n; ++i){
            tt[i] = t[hiddenarray[i]];
        }
        t = tt;
    }
}

bool check_element(string s){
    for (string t: v){
        if (s == t) return 1;
    }
    return 0;
}*/

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

void dncreturnans(int l, int r, string s){
    vector <int> left, right;
    for (int i = 0; i < n; ++i){
        if (s[i] == '0'){
            s[i] = '1';
            if (check_element(s)){
                left.pb(i);
            }
            else right.pb(i);
            s[i] = '0';
        }
    }
    if (r - l == 1){
        a[left[0]] = l - 1;
        a[right[0]] = r - 1;
        return;
    }
    int m = (l + r) / 2;
    for (int i: right) s[i] = '1';
    dncreturnans(l, m, s);
    for (int i: right) s[i] = '0';
    for (int i: left) s[i] = '1';
    dncreturnans(m + 1, r, s);
}

vector <int> restore_permutation(int N, int w, int r){
    n = N;
    vector <int> b;
    dnc(1, n);
    compile_set();
    string s;
    for (int i = 1; i <= n; ++i) s += '0';
    dncreturnans(1, n, s);
    for (int i = 0; i < n; ++i) b.pb(a[i]);
    return b;
}

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