oj.uz

Submission #590948

# Submission time Handle Problem Language Result Execution time Memory
590948 2022-07-06T15:23:14 Z Josia Unscrambling a Messy Bug (IOI16_messy) C++14
0 / 100
 12 ms 676 KB 
#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) {

    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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB grader returned WA
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB n = 32
2 Correct 3 ms 212 KB n = 32
3 Correct 2 ms 340 KB n = 32
4 Correct 2 ms 212 KB n = 32
5 Correct 2 ms 340 KB n = 32
6 Correct 2 ms 212 KB n = 32
7 Correct 2 ms 212 KB n = 32
8 Incorrect 2 ms 212 KB grader returned WA
9 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 300 KB n = 32
2 Correct 2 ms 212 KB n = 32
3 Incorrect 2 ms 212 KB grader returned WA
4 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 596 KB grader returned WA
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 676 KB grader returned WA
2 Halted 0 ms 0 KB -