Submission #836404

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

messy

#include <bits/stdc++.h>
#include <vector>
using namespace std;
#include "messy.h"

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;

int N;
string alf = "01";

string str(vi mask){
    string s = "";
    rep(c1,0,N){
        s += alf[mask[c1]];
    }
    return s;
}

vi add(vi mask, int i){
    mask[i] = 1;
    return mask;
}

void write_dq(int lo, int hi, vi mask){
    //cerr << lo << " " << hi << "\n";
    if(lo == hi-1)return;
    int mid = (lo+hi)/2;
    vi mask2 = mask;
    vi mask3 = mask;
    rep(c1,lo,mid){
        mask2[c1] = 1;
    }
    rep(c1,mid,hi){
        mask3[c1] = 1;
    }
    rep(c1,lo,mid){
        string s = str(add(mask, c1));
        add_element(s);
      //  cerr << s << "\n";
    }
    write_dq(lo,mid,mask3);
    write_dq(mid,hi,mask2);

}

int ANS[400] = {0};

void read_dq(int lo, int hi, vi mask){
    if(lo == hi-1){
        int smalls = 0;
        rep(c1,0,N){
            if(mask[c1] == 0){
                ANS[lo] = c1;
                smalls++;
            }
        }
        return;
    }
    int mid = (lo+hi)/2;
    vi mask2 = mask;
    vi mask3 = mask;

    rep(c1,0,N){
        if(mask[c1] == 0){
            string s = str(add(mask, c1));
            bool hej = check_element(s);
            if(hej){
                // was in left half
                mask2[c1] = 1;
            }
            else{
                mask3[c1] = 1;
            }
          //  cerr << s << "  ->  " << hej << "\n";
        }
    }

    read_dq(lo,mid,mask3);
    read_dq(mid,hi,mask2);

}

std::vector<int> restore_permutation(int n, int w, int r) {
    N = n;
    
    vi mask(n, 0);
    write_dq(0, n, mask);
  //  cerr << "WRITE DONE\n\n";
    compile_set();

    read_dq(0, n, mask);

    vi ans(n, 0);
    rep(c1,0,n){
        ans[ANS[c1]] = c1;
        //ans[c1] = ANS[c1];
    }

    return ans;
}

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