Submission #590950

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

messy

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

#include "messy.h"

using namespace std;



void ADDELEM(vector<bool> a) {
    string s;
    for (bool i: a) {
        if (i) s.push_back('1');
        else s.push_back('0');
    }


    // cerr << "added: " << s << "\n";


    add_element(s);
}



bool CHECKELEM(vector<bool> a) {
    string s;
    for (bool i: a) {
        if (i) s.push_back('1');
        else s.push_back('0');
    }

    bool res = check_element(s);

    // cerr << "checked: " << s << ": " << (int)res << "\n";

    return res;
}



std::vector<int> restore_permutation(int n, int w, int r) {

    // assert(n==128);

    int l = log2(n);

    vector<bool> mask(n, 0);
    for (int i = l-1; i>=0; i--) {
        vector<bool> add = mask;
        // if (i == 0) {
        //     for (int j = 0; j<n; j++) add[j] = !add[j];
        // }

        for (int j = 0; j<n; j++) {
            if ((j & (1<<i)) == 0) {
                add[j] = !add[j];
                mask[j] = 1;
                ADDELEM(add);
                add[j] = !add[j];
            }
        }
    }


    vector<bool> lastOne(n, 0);
    lastOne[0] = 1;
    lastOne[n-3] = 1;



    compile_set();


    vector<int> res(n);

    mask.assign(n, 0);
    for (int i = l-1; i>=0; i--) {
        vector<bool> add = mask;
        // if (i == 0) {
        //     for (int j = 0; j<n; j++) add[j] = !add[j];
        // }

        for (int j = 0; j<n; j++) {
            add[j] = !add[j];
            int tmpResp = CHECKELEM(add);
            add[j] = !add[j];
            if (tmpResp) {
                mask[j] = 1;
            }
            else {
                res[j] += 1<<i;
            }
        }
    }

    int indexOfFirst;

    for (int i = 0; i<n; i++) {
        if(res[i] == 0) {
            indexOfFirst = i;
        }
    }

    vector<int> badIndicies;

    for (int i = 0; i<n; i++) {
        if(res[i] == n-4) {
            badIndicies.push_back(i);
        }
    }

    // cerr << badIndicies.size() << "\n";
    assert(badIndicies.size() == 2);

    vector<bool> ask(n, 0);
    ask[indexOfFirst] = 1;
    ask[badIndicies[0]] = 1;

    if (CHECKELEM(ask)) res[badIndicies[0]]++;
    else res[badIndicies[1]]++;

    return res;
}

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