oj.uz

Submission #427145

# Submission time Handle Problem Language Result Execution time Memory
427145 2021-06-14T12:47:52 Z InternetPerson10 Unscrambling a Messy Bug (IOI16_messy) C++17
100 / 100
 5 ms 588 KB 
#include <vector>
#include <bits/stdc++.h>
#include "messy.h"

using namespace std;

bool arr[128];
vector<int> ans, ans2;
vector<vector<int>> nums;
string arrTo() {
    string s = "";
    for(int i = 0; i < ans.size(); i++) {
        s += (arr[i] ? "1" : "0"); 
    }
    // cout << s << '\n';
    return s;
}

vector<int> restore_permutation(int n, int w, int r) {
    int g = 0, x = 1;
    while(x != n) {
        g++; x *= 2;
    }
    ans.resize(n); ans2.resize(n);
    for(int i = 0; i < n; i++) {
        arr[i] ^= true;
        for(int j = 2; j < g; j++) {
            int k = (i | ((1 << j) - 1)) - ((1 << j) - 1);
            for(int m = 0; m < (1 << j); m++) {
                arr[k+m] ^= true; // flips all in the 2^j block
            }
            if(i & (1 << (j-1))) add_element(arrTo());
            for(int m = 0; m < (1 << j); m++) {
                arr[k+m] ^= true; 
            }
        }
        if(i >= n/2) {
            for(int j = 0; j < n; j++) arr[j] ^= true;
            // cout << "big: ";
            add_element(arrTo());
            for(int j = 0; j < n; j++) arr[j] ^= true;
        }
        if(i%2 == 1) {
            // cout << "odd: ";
            add_element(arrTo());
        }
        arr[i] ^= true;
    }
    // cout << "Compiled set!\n";
    compile_set();
    for(int i = 0; i < n; i++) { // determine odd/even
        arr[i] ^= true;
        if(check_element(arrTo())) ans[i]++;
        arr[i] ^= true;
    }
    for(int i = 0; i < n; i++) arr[i] ^= true;
    nums.resize(2);
    for(int i = 0; i < n; i++) { // determine wrt n/2
        arr[i] ^= true;
        if(check_element(arrTo())) {
            nums[1].push_back(i);
            ans[i] += (1 << (g-1));
        }
        else nums[0].push_back(i);
        arr[i] ^= true;
    }
    for(int i = 0; i < n; i++) arr[i] ^= true;
    int curr = 0; // current process vector
    int curg = 0; // bit currently being processed
    while(curr != nums.size()) {
        int k = 1;
        curg = 0;
        int ne = nums.size(); 
        while(k != nums[curr].size()) {
            curg++; k *= 2;
        }
        if(curg > 2) {
            nums.push_back(vector<int>());
            nums.push_back(vector<int>());
        }
        for(int i = 0; i < nums[curr].size(); i++) {
            arr[nums[curr][i]] ^= true;
        }
        for(int i = 0; i < nums[curr].size(); i++) {
            // cout << nums[curr][i] << ' ';
            arr[nums[curr][i]] ^= true;
            if(check_element(arrTo())) {
                ans[nums[curr][i]] += (1 << (curg-1));
                if(curg > 2) nums[ne].push_back(nums[curr][i]);
            }
            else if(curg > 2) nums[ne+1].push_back(nums[curr][i]);
            arr[nums[curr][i]] ^= true;
        }
        // cout << '\n';
        for(int i = 0; i < nums[curr].size(); i++) {
            arr[nums[curr][i]] ^= true;
        }
        curr++;
    }
    // for(int i = 0; i < n; i++) ans2[ans[i]] = i;
    return ans;
}

Compilation message

messy.cpp: In function 'std::string arrTo()':
messy.cpp:12:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for(int i = 0; i < ans.size(); i++) {
      |                    ~~^~~~~~~~~~~~
messy.cpp: In function 'std::vector<int> restore_permutation(int, int, int)':
messy.cpp:70:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     while(curr != nums.size()) {
      |           ~~~~~^~~~~~~~~~~~~~
messy.cpp:74:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         while(k != nums[curr].size()) {
      |               ~~^~~~~~~~~~~~~~~~~~~~
messy.cpp:81:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         for(int i = 0; i < nums[curr].size(); i++) {
      |                        ~~^~~~~~~~~~~~~~~~~~~
messy.cpp:84:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         for(int i = 0; i < nums[curr].size(); i++) {
      |                        ~~^~~~~~~~~~~~~~~~~~~
messy.cpp:95:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         for(int i = 0; i < nums[curr].size(); i++) {
      |                        ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB n = 32
2 Correct 1 ms 204 KB n = 32
3 Correct 1 ms 296 KB n = 32
4 Correct 1 ms 332 KB n = 32
5 Correct 1 ms 204 KB n = 32
6 Correct 1 ms 204 KB n = 32
7 Correct 1 ms 204 KB n = 32
8 Correct 1 ms 204 KB n = 32
9 Correct 2 ms 204 KB n = 32
10 Correct 1 ms 204 KB n = 32
11 Correct 1 ms 204 KB n = 32
12 Correct 1 ms 204 KB n = 32
13 Correct 1 ms 256 KB n = 32
14 Correct 1 ms 288 KB n = 32
15 Correct 1 ms 204 KB n = 32

Subtask #4
21.0 / 21.0

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

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 432 KB n = 128
2 Correct 5 ms 460 KB n = 128
3 Correct 4 ms 460 KB n = 128
4 Correct 5 ms 460 KB n = 128
5 Correct 5 ms 460 KB n = 128
6 Correct 5 ms 584 KB n = 128
7 Correct 3 ms 460 KB n = 128
8 Correct 3 ms 460 KB n = 128
9 Correct 3 ms 416 KB n = 128
10 Correct 4 ms 588 KB n = 128
11 Correct 4 ms 480 KB n = 128
12 Correct 4 ms 420 KB n = 128
13 Correct 4 ms 420 KB n = 128
14 Correct 4 ms 500 KB n = 128
15 Correct 4 ms 420 KB n = 128