Submission #1019962

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019962		ProtonDecay314	Unscrambling a Messy Bug (IOI16_messy)	C++17	100 / 100	2 ms	856 KiB

messy

// AM+DG

/*

*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<bool> vb;
#define L(i, varmn, varmx) for(ll i = varmn; i < varmx; i++)
#define LR(i, varmx, varmn) for(ll i = varmx; i > varmn; i--)
#define LI(i, varmn, varmx) for(int i = varmn; i < varmx; i++)
#define LIR(i, varmx, varmn) for(int i = varmx; i > varmn; i--)
#define pb push_back
#include "messy.h"

// #define DEBUG

// string to_binstring(int num, int n) {
//     string res;

//     LI(i, 0, n) {
//         res.pb(((num >> i) & 0b1 ? '1' : '0'));
//     }

//     assert((int)res.size() == n);

//     return res;
// }

void write(int orig_n, int n, int l, int r) {
    string cur_mask(orig_n, '1');

    LI(i, l, r + 1) {
        cur_mask[i] = '0';
    }

    string to_push;
    LI(i, 0, n >> 1) {
        to_push = cur_mask;
        to_push[i + l] = '1';

        add_element(to_push);
    }

    if(n > 2) {
        int m = (l + r) >> 1;
        write(orig_n, n >> 1, l, m);
        write(orig_n, n >> 1, m + 1, r); // This is starting to look like segtree code LOL
    }
}

void solve(int orig_n, int n, int offset, const set<int>& inds, vi& ans) {
    set<int> left;
    set<int> right;

    string base_mask(orig_n, '1');
    for(int i : inds) {
        base_mask[i] = '0';
    }

    string cur_mask;
    
    for(int i : inds) {
        cur_mask = base_mask;
        cur_mask[i] = '1';

        (check_element(cur_mask) ? left : right).insert(i);        
    }

    if(n > 2) {
        solve(orig_n, n >> 1, offset, left, ans);
        solve(orig_n, n >> 1, offset + (n >> 1), right, ans);
    } else {
        // cout << "KIMI DAYO KIMI NANDAYO " << *(left.begin()) << " " << *(right.begin()) << endl;
        // (If you're reading this, I was listening to YLIA OST while coding so yeah, haha)

        // The thing in the left set is index offset
        ans[*(left.begin())] = offset;

        // The thing in the right set is index offset + (n >> 1)
        ans[*(right.begin())] = offset + (n >> 1);
    }
}

vi restore_permutation(int n, int w, int r) {
    
    // Write Elements
    write(n, n, 0, n - 1);

    // Compile the set!
    compile_set();

    // Solve!
    vi ans(n, -1);
    set<int> inds;
    LI(i, 0, n) inds.insert(i);
    solve(n, n, 0, inds, ans);

    // LI(i, 0, n) {
    //     cout << ans[i] << " ";
    // }
    // cout << endl;

    return ans;
}

#ifdef DEBUG
int main() {

}
#endif

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