Submission #1305271

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

messy

#include<bits/stdc++.h>
#include "messy.h"
using namespace std;
vector<int> restore_permutation(int n, int w, int r){
    vector<int>resp(n);
    int b=__lg(n);
    for(int i=0;i<b-1;i++){
        string s="";
        for(int j=0;j<=i;j++) s.push_back('0');
        for(int j=i+1;j<n;j++) s.push_back('1');
        add_element(s); // descobrir b-1 caras para usar com os bits dps
    }    
    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[i]='1'; // coloco os k's bits q ja se a posicao
        for(int i=b-1;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';
            }
        }
    }
    compile_set();
    for(int i=0;i<b-1;i++){
        string s="";
        for(int j=0;j<n;j++) s.push_back('1');
        for(int j=0;j<i;j++) s[resp[j]]='0'; // settando os caras q eu ja sei q sao 0's 
        for(int j=0;j<n;j++){
            if(s[j]=='0') continue; // ja ta pareado
            s[j]='0';
            if(check_element(s)){ // checando se eh a minha posicao
                resp[i]=j;
                break;
            }
            s[j]='1';
        }
    }
    vector<int>aux(n,0);
    for(int i=0;i<b-1;i++) aux[resp[i]]=-1; // tirando as incoveniencias 
    for(int k=0;k<b;k++){
        string s="";
        for(int i=0;i<n;i++) s.push_back('0');
        for(int j=0;j<k;j++) s[resp[j]]='1'; // settando o seu correspondente
        for(int i=0;i<n;i++){
            if(s[i]=='1') continue;
            s[i]='1';
            if(check_element(s)) aux[i]+=(1<<k);
            s[i]='0';
        }
    }
    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