Submission #711588

#	Time	Username	Problem	Language	Result	Execution time	Memory
711588		TimDee	Unscrambling a Messy Bug (IOI16_messy)	C++17	49 / 100	1 ms	340 KiB

messy

#include "messy.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
vector<int> restore_permutation(int n, int w, int r) {

    //1000
    //0100
    //? 1000 -> yes=>(1)/no=>(2)
    //(1): 
    //1100 -> 1010
    //(n/k)*(n/k)/2*k
    //n*n/2k
    // O(32) 11110000 -> 01100101
    // O(16*15/2) = O(8*15) = 120 for ?p[i], i>=n/2
    // O(16*15/2) = O(8*15) = 120 for ?p[i], i<n/2
    if (n>32) return vector<int>(n,-1);
    string z(n,'0');
    forn(i,n/2) {
        z[i]='1';
        add_element(z);
        z[i]='0';
    }
    for (int i=n-1; i>=n/2; --i) z[i]='1';
    for (int i=n/2-1; i>=0; --i) {
        z[i]='1';
        add_element(z);
    }
    for (int i=n-1; i>=n/2; --i) {
        z[i]='0';
        add_element(z);
    }
    compile_set();
    z.assign(n,'0');
    string ans(n,'0');
    vector<int> p(n,-1);
    vector<int> paiu;
    forn(i,n) {
        z[i]='1';
        int x=check_element(z);
        if (x) {
            ans[i]='1';
            paiu.push_back(i);
        }
        z[i]='0';
    }
    for (int i=n/2; i<n; ++i) {
        forn(j,n) {
            if (ans[j]=='1') continue;
            ans[j]='1';
            int x=check_element(ans);
            if (x) {
                p[j]=i;
                break;
            }
            ans[j]='0';
        }
    }
    assert(ans==string(n,'1'));
    for(auto&x:paiu) ans[x]='0';
    for (int i=n/2-1; i>=0; --i) {
        forn(j,n) {
            if (ans[j]=='1') continue;
            ans[j]='1';
            int x=check_element(ans);
            if (x) {
                p[j]=i;
                break;
            }
            ans[j]='0';
        }
    }
    assert(ans==string(n,'1'));
    return p;

}

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