oj.uz

Submission #590957

# Submission time Handle Problem Language Result Execution time Memory
590957 2022-07-06T15:56:05 Z Josia Unscrambling a Messy Bug (IOI16_messy) C++14
100 / 100
 4 ms 596 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);
}

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

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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 292 KB n = 8
2 Correct 0 ms 212 KB n = 8
3 Correct 0 ms 212 KB n = 8
4 Correct 0 ms 212 KB n = 8
5 Correct 0 ms 212 KB n = 8
6 Correct 0 ms 212 KB n = 8
7 Correct 0 ms 212 KB n = 8
8 Correct 0 ms 212 KB n = 8
9 Correct 0 ms 212 KB n = 8
10 Correct 0 ms 212 KB n = 8
11 Correct 0 ms 212 KB n = 8
12 Correct 0 ms 212 KB n = 8
13 Correct 0 ms 212 KB n = 8
14 Correct 0 ms 212 KB n = 8
15 Correct 1 ms 212 KB n = 8

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 32
2 Correct 1 ms 212 KB n = 32
3 Correct 1 ms 212 KB n = 32
4 Correct 1 ms 212 KB n = 32
5 Correct 1 ms 212 KB n = 32
6 Correct 0 ms 212 KB n = 32
7 Correct 1 ms 212 KB n = 32
8 Correct 1 ms 212 KB n = 32
9 Correct 1 ms 212 KB n = 32
10 Correct 1 ms 212 KB n = 32
11 Correct 1 ms 212 KB n = 32
12 Correct 1 ms 212 KB n = 32
13 Correct 1 ms 212 KB n = 32
14 Correct 1 ms 316 KB n = 32
15 Correct 1 ms 340 KB n = 32

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 32
2 Correct 1 ms 212 KB n = 32
3 Correct 1 ms 212 KB n = 32
4 Correct 1 ms 384 KB n = 32
5 Correct 1 ms 212 KB n = 32
6 Correct 1 ms 212 KB n = 32
7 Correct 1 ms 212 KB n = 32
8 Correct 1 ms 212 KB n = 32
9 Correct 1 ms 212 KB n = 32
10 Correct 1 ms 212 KB n = 32
11 Correct 0 ms 212 KB n = 32
12 Correct 1 ms 212 KB n = 32
13 Correct 1 ms 212 KB n = 32
14 Correct 1 ms 212 KB n = 32
15 Correct 1 ms 212 KB n = 32

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB n = 128
2 Correct 3 ms 596 KB n = 128
3 Correct 3 ms 596 KB n = 128
4 Correct 3 ms 596 KB n = 128
5 Correct 3 ms 596 KB n = 128
6 Correct 3 ms 596 KB n = 128
7 Correct 3 ms 468 KB n = 128
8 Correct 3 ms 596 KB n = 128
9 Correct 3 ms 596 KB n = 128
10 Correct 4 ms 596 KB n = 128
11 Correct 3 ms 484 KB n = 128
12 Correct 3 ms 596 KB n = 128
13 Correct 3 ms 596 KB n = 128
14 Correct 3 ms 596 KB n = 128
15 Correct 3 ms 468 KB n = 128

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB n = 128
2 Correct 3 ms 556 KB n = 128
3 Correct 3 ms 596 KB n = 128
4 Correct 3 ms 596 KB n = 128
5 Correct 3 ms 596 KB n = 128
6 Correct 3 ms 596 KB n = 128
7 Correct 3 ms 556 KB n = 128
8 Correct 4 ms 596 KB n = 128
9 Correct 3 ms 596 KB n = 128
10 Correct 3 ms 596 KB n = 128
11 Correct 4 ms 596 KB n = 128
12 Correct 3 ms 596 KB n = 128
13 Correct 3 ms 560 KB n = 128
14 Correct 3 ms 596 KB n = 128
15 Correct 3 ms 556 KB n = 128