Submission #1095677

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

messy

#include <bits/stdc++.h> 
using namespace std;
#define pb push_back 
#define is insert
#define lb lower_bound
#define ll long long
#define V vector
#define MS multiset
#define PL pair<ll, ll>
#define F first
#define S second
#define PQ priority_queue
#define f0r(i, begin, end) for (ll i = begin; i < end; i ++) 
#define For(i, end, begin) for (ll i = end; i > begin; i --) 
#define all(x) x.begin(), x.end()
#define INF 1000000000000000000
#define inf 1000000000
#define MOD 1000000007
#define len(x) (ll)x.size()
#define fileread(file) ifstream fin; fin.open((string)file + ".in"); ofstream fout; fout.open((string)file + ".out")
#define fastio ios_base::sync_with_stdio(0); cin.tie(nullptr)
template<typename T> istream& operator>>(istream& in, vector<T>& a) {for(auto &x : a) in >> x; return in;};
template<typename T> ostream& operator<<(ostream& out, vector<T>& a) {for(auto &x : a) out << x << ' '; return out;};

#include "messy.h"

/* 
Remove

V<string> OS;
V<int> permute;

void add_element (string s) {
    OS.pb(s);
}

void compile_set () {
    V<string> opS;
    for (auto s : OS) {
        string os = s;
        f0r (i, 0, len(permute)) {
            os[i] = s[permute[i]];
        }
        opS.pb(os);
    }

    f0r (i, 0, len(OS)) {
        OS[i] = opS[i];
    }
}

bool check_element (string x) {
    for (auto p : OS) {
        if (p == x) return true;
    }
    return false;
}
*/

V<int> restore_permutation (int n, int w, int r) {
    queue<pair<int, int>> q;
    q.push({0, n});
    V<string> binstrings;
    V<tuple<string, int, int>> bases;

    while (!q.empty()) {
        int l = q.front().F, r = q.front().S;
        q.pop();

        ll avg = (l + r) / 2;
        if (r - l == 1) {
            continue;
        }

        string base;
        f0r (i, 0, l) base += '1';
        f0r (i, l, r) base += '0';
        f0r (i, r, n) base += '1';
        bases.pb({base, l, r});

        f0r (i, avg, r) {
            string alt = base;
            alt[i] = '1';
            binstrings.pb(alt);
        }

        q.push({avg, r});
        q.push({l, avg});
    }
    
    for (auto b : binstrings) {
        add_element(b);
    }
    compile_set();

    map<string, string> baseconv;
    string all0, all1;
    f0r (i, 0, n) {
        all0 += '0';
        all1 += '1';
    }
    baseconv[all0] = all0;

    V<int> ans(n, 0);

    for (auto b : bases) {
        string base = get<0>(b);
        int l = get<1>(b), r = get<2>(b);
        int midp = (r + l) / 2;

        string convbase = baseconv[base];
        string norm = convbase; // 000111
        string antinorm = convbase; // 111000

        f0r (i, 0, n) {
            if (convbase[i] == '1') continue;

            string alt = convbase;
            alt[i] = '1';
            
            if (check_element(alt)) {
                norm[i] = '1';
                ans[i] += (r - midp);
            } else {
                antinorm[i] = '1';
            }
        }

        string normbase = base, antibase = base;
        f0r (i, midp, r) normbase[i] = '1';
        f0r (i, l, midp) antibase[i] = '1';

        baseconv[normbase] = norm;
        baseconv[antibase] = antinorm;
    }

    return ans;
}

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