Submission #590957

#	Time	Username	Problem	Language	Result	Execution time	Memory
590957		Josia	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	4 ms	596 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);
}

map<string, int> dict;

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

    if (dict.count(s) != 0) return dict[s];

    bool res = check_element(s);

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

    return dict[s] = res;
}



std::vector<int> restore_permutation(int n, int w, int r) {
    dict.clear();

    // 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;

    ADDELEM(lastOne);



    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++) {
        // cerr << res[i] << " ";
        if(res[i] == 0) {
            indexOfFirst = i;
        }
    }
    // cerr << "\n";

    vector<int> badIndicies;

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

    // cerr << badIndicies[0] << " " << badIndicies[1] << "\n";
    // assert(badIndicies.size() == 2);

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

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

    return res;
}

Compilation message (stderr)

messy.cpp: In function 'bool CHECKELEM(std::vector<bool>)':
messy.cpp:39:20: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   39 |     return dict[s] = res;

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