Submission #1074270

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

messy

#include <bits/stdc++.h>
#include "messy.h"
using namespace std;
bool visited[128];
vector<int> ansarr;
int mnmx[128][2];


void recuradd(pair<int,int> range, int n) {
    string sus(n, '1');
    for (int i=range.first;i<=range.second;i++) {
        sus[i] = '0';
    }
    int mid = (range.first + range.second + 1) / 2;
    for (int i=mid;i<=range.second;i++) {
        sus[i] = '1';
        add_element(sus);
        sus[i] = '0';
    }
    if (range.second - range.first != 1) {
        recuradd(make_pair(range.first, mid - 1), n);
        recuradd(make_pair(mid, range.second), n);
    }
}


void recurcheck(pair<int,int> range, int n) {
    string sus(n, '1');
    for (int i=0;i<n;i++) {
        if (mnmx[i][0] >= range.first && mnmx[i][1] <= range.second) {
            sus[i] = '0';
        }
    }
    int mid = (range.first + range.second + 1) / 2;
    for (int i=0;i<n;i++) {
        if (sus[i] == '0') {
            sus[i] = '1';
            if (check_element(sus)) {
                mnmx[i][0] = mid;
                if (mnmx[i][0] == mnmx[i][1]) {
                    ansarr[i] = mnmx[i][0];
                }
            } else {
                mnmx[i][1] = mid - 1;
                if (mnmx[i][0] == mnmx[i][1]) {
                    ansarr[i] = mnmx[i][0];
                }
            }
            sus[i] = '0';
        }
    }
    if (range.second - range.first != 1) {
        recurcheck(make_pair(range.first, mid - 1), n);
        recurcheck(make_pair(mid, range.second), n);
    }
}



vector<int> restore_permutation(int n, int w, int r) {
    recuradd(make_pair(0, n - 1), n);
    compile_set();


    for (int i=0;i<n;i++) {
        ansarr.push_back(-1);
        mnmx[i][0] = 0; mnmx[i][1] = n - 1;
    }
    recurcheck(make_pair(0, n - 1), n);
    
    return ansarr;
}

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