Submission #419858

#	Time	Username	Problem	Language	Result	Execution time	Memory
419858		Peti	Unscrambling a Messy Bug (IOI16_messy)	C++14	20 / 100	2 ms	460 KiB

messy

#include <bits/stdc++.h>

#include "messy.h"

using namespace std;

const int codeM = 4;

vector<int> codes = {5, 7, 10, 11, 13, 14};
void add_start(int n){
    string s;
    s.assign(n, '0');
    s[0] = '1';
    add_element(s);

    for(int i = 1; i < codeM; i++){
        s.assign(n, '0');
        s[i-1] = s[i] = '1';
        add_element(s);
    }
}

int pos[codeM];
void set_code(string &s, int c){
    for(int i = 0; i < codeM; i++)
        if(c&(1<<i))
            s[pos[i]] = '1';
}

void add(int l, int r, int x, int n){
    if(l+1 >= r) return;
    int m = (l+r)/2;
    string s;
    s.assign(n, '0');
    set_code(s, codes[x]);
    for(int i = l; i < m; i++){
        s[i] = '1';
        add_element(s);
        s[i] = '0';
    }
    add(l, m, x+1, n);
    add(m, r, x+1, n);
}

int irany[128][6];
bool volt[128] = {};
void get_start(int n){
    for(int i = 0; i < n; i++){
        string s;
        s.assign(n, '0');
        s[i] = '1';
        if(check_element(s)){
            pos[0] = i;
            break;
        }
    }
    volt[0] = true;
    for(int i = 1; i < codeM; i++){
        for(int j = 0; j < n; j++){
            if(j == pos[i-1] || volt[j]) continue;
            string s;
            s.assign(n, '0');
            s[pos[i-1]] = s[j] = '1';
            if(check_element(s)){
                pos[i] = j;
                break;
            }
        }
        volt[pos[i]] = true;
    }
}

std::vector<int> restore_permutation(int n, int w, int r) {
    for(int i = 0; i < codeM; i++)
        pos[i] = i;
    add_start(n);
    add(codeM, n, 0, n);
    //cout<<"added"<<endl;
    compile_set();
    //cout<<"compiled"<<endl;
    get_start(n);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < 6; j++)
            irany[i][j] = 1;
    for(int i = 0; i < 6; i++){
        string s;
        s.assign(n, '0');
        set_code(s, codes[i]);
        for(int j = 0; j < n; j++){
            if(s[j] == '1') continue;
            s[j] = '1';
            if(check_element(s))
                irany[j][i] = 0;
            s[j] = '0';
        }
    }

    vector<int> ret(n, -1);
    for(int i = 0; i < codeM; i++)
        ret[pos[i]] = i;
    for(int i = 0; i < n; i++){
        if(ret[i] != -1) continue;
        int l = 4, r = n;
        for(int j = 0; j < 6; j++){
            int m = (l+r)/2;
            if(irany[i][j])
                l = m;
            else
                r = m;
        }
        ret[i] = l;
    }

    return ret;
}

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