Submission #570127

#	Time	Username	Problem	Language	Result	Execution time	Memory
570127		davi_bart	Unscrambling a Messy Bug (IOI16_messy)	C++17	50 / 100	2 ms	468 KiB

messy

#pragma GCC optimize("O3")
#pragma GCC target("popcnt")
#include <bits/stdc++.h>

#include "messy.h"
using namespace std;
#define ll long long
#define fi first
#define se second
#define pb push_back
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
string zeri;
int N;
void add() {
    string k = string(N, '1');
    k[0] = '0';
    add_element(k);
    for (int i = 0; i < 7; i++) {
        string x = zeri;
        x[i] = '1';
        add_element(x);
        for (int j = 0; j < i; j++) x[j] = '1';
        add_element(x);
    }
    for (int i = 7; i < N; i++) {
        for (int j = 0; j < 7; j++) {
            if (i & (1 << j)) {
                string k = zeri;
                k[0] = k[1] = k[2] = k[3] = k[4] = k[5] = k[6] = '1';
                k[j] = '0';
                k[i] = '1';
                add_element(k);
            }
        }
    }
}
vector<int> base(8);
vector<int> ans(200);
void get_basi() {
    vector<int> options;
    for (int i = 0; i < N; i++) {
        string k = zeri;
        k[i] = '1';
        if (check_element(k)) options.pb(i);
    }
    for (int i = 0; i < options.size(); i++) {
        string k = string(N, '1');
        k[options[i]] = '0';
        if (check_element(k)) {
            base[0] = options[i];
            options.erase(options.begin() + i);
            break;
        }
    }
    string cur = zeri;
    cur[base[0]] = '1';
    for (int i = 1; i < 7; i++) {
        for (int j = 0; j < options.size(); j++) {
            string k = cur;
            k[options[j]] = '1';
            if (check_element(k)) {
                base[i] = options[j];
                options.erase(options.begin() + j);
                cur = k;
                break;
            }
        }
    }
    for (int i = 0; i < 7; i++) {
        // cout << base[i] << " ";
    }
    // cout << endl;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < 7; j++) {
            string k = zeri;
            k[base[0]] = k[base[1]] = k[base[2]] = k[base[3]] = k[base[4]] = k[base[5]] = k[base[6]] = '1';
            k[base[j]] = '0';
            k[i] = '1';
            if (check_element(k)) {
                ans[i] += (1 << j);
            }
        }
    }
    for (int i = 0; i < 7; i++) {
        // cout << ans[base[i]] << " ";
        ans[base[i]] = i;
    }
    // cout << endl;
    // for (int i = 0; i < N; i++) cout << ans[i] << " ";
    // cout << endl;
}
std::vector<int> restore_permutation(int n, int w, int r) {
    N = n;
    zeri = string(N, '0');
    add();
    compile_set();
    get_basi();
    ans.resize(N);
    return ans;
}

Compilation message (stderr)

messy.cpp: In function 'void get_basi()':
messy.cpp:46:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for (int i = 0; i < options.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~
messy.cpp:58:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         for (int j = 0; j < options.size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~~

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