Submission #1211667

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211667		sano	Unscrambling a Messy Bug (IOI16_messy)	C++20	100 / 100	1 ms	584 KiB

messy

#include "messy.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#include <cassert>
#include <bitset>
#include <random>
#include <chrono>
#include <cstring>
#define shit short int
#define ll long long
#define ld long double
//#define int ll
#define For(i, n) for(int i = 0; i < (int)n; i++)
#define ffor(i, a, n) for(int i = (int)a; i < (int)n; i++)
#define rfor(i, n) for(int i = (int)n; i >= (int)0; i--)
#define rffor(i, a, n) for(int i = (int)n; i >= (int)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<int, int>
#define pld pair<ld, ld>
#define NEK 2000000000000000
#define mod 1000000007
#define mod2 1000000009
#define rsz resize 
#define prv 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define all(x) (x).begin(), (x).end()
#define sig 0.0000001

using namespace std;
/*
set<string> s;
vec<int> pp;
void add_element(string x) {
    string x2;
    For(i, pp.size()) x2.push_back(x[i]);
    For(i, pp.size()) {
        x2[i] = x[pp[i]];
    }
    s.insert(x2);
    return;
}

bool check_element(string x) {
    return (s.find(x) != s.end());
}

void compile_set() {
    return;
}*/

int pocw = 0, pocr = 0;

void pridavaj(int a, int b, int n) {
    if (a == b) {
        return;
    }
    string x;
    For(i, n) x.push_back('1');
    ffor(i, a, b + 1) x[i] = '0';
    for (int j = a; j <= (a + b) / 2; j++) {
        x[j] = '1';
        pocw--;
        if (pocw < 0) {
            while (1) {
                cout << 1;
            }
        }
        add_element(x);
        x[j] = '0';
    }
    pridavaj(a, (a + b) / 2, n);
    pridavaj((a + b) / 2 + 1, b, n);
    return;
}

void zisti(vec<int>&p, int a, int b, int n, set<int>m) {
    if (a == b) {
        p[*m.begin()] = a;
        return;
    }
    string x;
    For(i, n) x.push_back('1');
    for(auto i : m) x[i] = '0';
    set<int> m2;
    for(auto i : m){
        x[i] = '1';
        pocr--;
        if (pocr < 0) {
            while (1) {
                cout << 1;
            }
        }
        bool je = check_element(x);
        if(je) m2.insert(i);
        x[i] = '0';
    }
    for (auto i : m2) m.erase(i);
    zisti(p, a, (a + b) / 2, n, m2);
    zisti(p, (a + b) / 2 + 1, b, n, m);
    return;
}


vec<int> restore_permutation(int n, int w, int r) {
    pocw = w, pocr = r;
    vec<int> p(n, -1);
    set<int>m;
    For(i, n) m.insert(i);
    string x;
    For(i, n) x.push_back('0');
    pridavaj(0, n-1, n);
    compile_set();
    zisti(p, 0, n - 1, n, m);
    return p;
}
/*
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, w, r; cin >> n;
    w = 10000, r = 10000;
    pp.resize(n);
    For(i, n) cin >> pp[i];
    vec<int> p = restore_permutation(n, w, r);
    For(i, p.size()) cout << p[i] << " \n"[i == (p.size() - 1)];
    return 0;
}*/

Compilation message (stderr)

messy.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
messy_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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