Submission #1305278

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305278		enzy	Unscrambling a Messy Bug (IOI16_messy)	C++20	70 / 100	2 ms	584 KiB

messy

#include<bits/stdc++.h>
#include "messy.h"
using namespace std;
void set_pot(int n, int b){
    string s="";
    for(int i=0;i<n;i++) s.push_back('1');
    for(int i=0;i<b;i++){
        int at=(1<<i); 
        s[at]='0';
        add_element(s);
        s[at]='1';
    }
}
vector<int> find_pot(int n, int b){
    vector<int>ret;
    string s="";
    for(int i=0;i<n;i++) s.push_back('1');
    for(int i=0;i<n-1;i++){
        s[i]='0';
        if(check_element(s)) ret.push_back(i);
        s[i]='1';
    }
    if(ret.size()<b) ret.push_back(n-1); // tinha no n-1
    return ret;
}
vector<int> restore_permutation(int n, int w, int r){
    vector<int>resp(n);
    int b=__lg(n);
    
    // descobrir os qm sao os p's das pot de 2
    set_pot(n,b); // faco query do tipo 10111..1 110111...1 11110111...1 com os 0's nas pot de 2

    for(int k=0;k<b;k++){ // passo por todos os bits
        string s="";
        for(int i=0;i<n;i++) s.push_back('0');
        for(int i=0;i<k;i++) s[(1<<i)]='1'; // coloco os k's bits q ja sei a posicao
        for(int i=0;i<n;i++){
            if(i&(1<<k)){  // se ele tem o bit faco query com ele
                s[i]='1';
                add_element(s);
                s[i]='0';
            }
        }
    } // pseudo bit-trick

    // w= b + qtd_bit(i)*n < n*log(n)

    compile_set(); // compilo tudo


    vector<int>possib=find_pot(n,b); // acho pra onde foram as pot de 2
    vector<int>aux(n,0);
    map<int,int> mp, pos, neg;
    for(int k=0;k<b;k++){
        mp.clear(); pos.clear(); neg.clear();
        // cout << "aux: ";
        // for(int x : aux){
        //     cout << x << ' ';
        //     mp[x]++;
        // }
        // cout << endl;
        string s="";
        for(int i=0;i<n;i++) s.push_back('0');
        for(int j=0;j<k;j++) s[resp[(1<<j)]]='1'; // settando o seu correspondente
        for(int i=0;i<n;i++){
            if(s[i]=='1'){
                neg[aux[i]]++; // como sou pot de 2, com ctz n somei nesse momento
                continue;
            }   
            if(pos[aux[i]]+neg[aux[i]]+1==mp[aux[i]]){ // se chequei todos menos 1, ja sei minha escolha
                // cout << aux[i] << " " << pos[aux[i]] << ' ' << neg[aux[i]] << endl;
                if(pos[aux[i]]<neg[aux[i]]) aux[i]+=(1<<k); // se minha escolha for pegar, somar
                continue;
            }
            s[i]='1';
            if(check_element(s)){   
                pos[aux[i]]++;
                aux[i]+=(1<<k);
                for(int x : possib) if(x==i) resp[(1<<k)]=i; // achei a potencia de 2 correspondente
            }else neg[aux[i]]++;
            s[i]='0';
        }
    }
    // cout << "aux: ";
    // for(int x : aux){
    //     cout << x << ' ';
    //     mp[x]++;
    // }
    // cout << endl;
    // r = (n-1) + n*log(n) - (1+2+4+8+...+n/2) = (n-1) + n*log(n) - (n-1) = n*log(n), yay
    for(int i=0;i<n;i++) if(aux[i]!=-1) resp[aux[i]]=i;
    vector<int>inv(n);
    for(int i=0;i<n;i++) inv[resp[i]]=i;
    return inv;
}

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: 0 / 30