Submission #427145

#	Time	Username	Problem	Language	Result	Execution time	Memory
427145		InternetPerson10	Unscrambling a Messy Bug (IOI16_messy)	C++17	100 / 100	5 ms	588 KiB

messy

#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 (stderr)

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 / 20
• Subtask 2: 18 / 18
• Subtask 3: 11 / 11
• Subtask 4: 21 / 21
• Subtask 5: 30 / 30