Submission #96120

#	Time	Username	Problem	Language	Result	Execution time	Memory
96120		lyc	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	4 ms	640 KiB

messy

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

#include "messy.h"
int N;

void add(int l, int r) {
    if (l == r) return;

    int m = (l+r)/2;
    string temp(N, '0');
    for (int i = 0; i < l; ++i) temp[i] = '1';
    for (int i = r+1; i < N; ++i) temp[i] = '1';

    for (int i = l; i <= m; ++i) {
        temp[i] = '1';
        //cout << "INSERT " << temp << endl;
        add_element(temp);
        temp[i] = '0';
    }

    add(l, m);
    add(m+1, r);
}

vector<int> check(int l, int r, string temp) {
    if (l == r) {
        vector<int> v;
        for (int i = 0; i < N; ++i) {
            if (temp[i] == '0') {
                v.push_back(i);
                break;
            }
        }
        return move(v);
    }

    int m = (l+r)/2;
    string a(temp), b(temp);
    for (int i = 0; i < N; ++i) {
        if (temp[i] == '0') {
            temp[i] = '1';
            bool exist = check_element(temp);
            //cout << "CHECK " << temp << ": " << exist << endl;
            temp[i] = '0';

            if (exist) b[i] = '1';
            else a[i] = '1';
        }
    }
   
    vector<int> lt = check(l, m, a);
    vector<int> rt = check(m+1, r, b);
    lt.insert(lt.end(), rt.begin(), rt.end());
    return lt;
}

std::vector<int> restore_permutation(int n, int w, int r) {
    N = n;
    add(0, n-1);
    compile_set();
    vector<int> goes = check(0, n-1, string(n, '0'));
    vector<int> perm(n);
    for (int i = 0; i < n; ++i) perm[goes[i]] = i;
    return perm;
}

/**
    10000000
    01000000
    00100000
    00010000
            8
    10001111
    01001111
            4
    10111111
            2
    11101111
            2

    11111000
    11110100
            4
    11111011
            2
    11111110
            2

    Total 24
 **/

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