Submission #1065649

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065649		Hectorungo_18	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	1 ms	632 KiB

messy

#include <bits/stdc++.h>
 
#include "messy.h"
using namespace std;
 
mt19937 gnd(time(nullptr));
 
// #define int long long
 
void ch(string& s, int pos, char c){
    s[pos]=c;
    return;
}
 
vector<int> restore_permutation(int n, int w, int r){
    int mxb = 6;
    int bb = 0;
    int aux  = n;
    while(aux > 1){
        bb++;
        aux/=2;
    }
    mxb = bb-1;
  
    string s (n, '0');
    char u = '1', c = '0';
    for(int bi = mxb; bi >= 0 ; bi--){
        if(bi == mxb){
            for(int i = n/2; i < n; i++){
                ch(s, i, u);
                add_element(s);
                ch(s, i, c);
            }
        }
        else{
            for(int i = 0; i < (1<<(bi+1)); i++){
                ch(s, i, u);
            }
            for(int i = n/2+(1<<bi); i < n; i+=(1<<(bi+1))){
                for(int j = i; j < i+(1<<(bi)); j++){
                    ch(s, j, u);
                    add_element(s);
                    ch(s, j, c);
                }
            }
            for(int i = 0; i < (1<<(bi+1)); i++){
                ch(s, i, c);
            }
 
            for(int i = n/2; i < n/2+(1<<(bi+1)); i++){
                ch(s, i, u);
            }
            for(int i = (1<<bi); i < n/2; i+=(1<<(bi+1))){
                for(int j = i; j < i+(1<<(bi)); j++){
                    ch(s, j, u);
                    add_element(s);
                    ch(s, j, c);
                }
            }
            for(int i = n/2; i < n/2+(1<<(bi+1)); i++){
                ch(s, i, c);
            }
        }
    }
 
    compile_set();
 
    vector<int> ans(n, 0);
    set<int> fh, sh;
    vector<int> ffh, ssh;
    for(int bi = mxb; bi >= 0; bi--){
        if(bi == mxb){
            for(int i = 0; i < n; i++){
                ch(s, i, u);
                int a = check_element(s);
                ch(s, i, c);
                if(a){
                    ans[i]+=(1<<bi);
                    sh.insert(i);
                    ssh.push_back(i);
                }
                else{
                    fh.insert(i);
                    ffh.push_back(i);
                }
            }
        }
        else{
            set<int> aux = sh;
            for(auto x : fh){
                ch(s, x, u);
            }  
            for(auto x : ssh){
                ch(s, x, u);
                int a = check_element(s);
                ch(s, x, c);
                if(a){
                    if(sh.count(x)) sh.erase(x);
                    ans[x]+=(1<<bi);
                }
                // else{
 
                // }
            }
            for(auto x : fh){
                ch(s, x, c);
            }
 
 
            for(auto x : aux){
                ch(s, x, u);
            }
            for(auto x : ffh){
                ch(s, x, u);
                int a = check_element(s);
                ch(s, x, c);
                if(a){
                    if(fh.count(x)) fh.erase(x);
                    ans[x]+=(1<<bi);
                }
            }
            
            for(auto x : aux){
                ch(s, x, c);
              
            }
 
        }
    }   
 
    return ans;
}
 

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