Submission #291157

#	Time	Username	Problem	Language	Result	Execution time	Memory
291157		peti1234	Unscrambling a Messy Bug (IOI16_messy)	C++17	100 / 100	3 ms	564 KiB

messy

#include <bits/stdc++.h>
#include "messy.h"
using namespace std;
string s;
const int c=128;
vector<int> dp;
int n, po;
vector<int> restore_permutation(int x, int w, int r) {
    n=x, po=x;
    for (int i=0; i<n; i++) s+='0', dp.push_back(0);
    while(po>1) {
        for (int i=0; i<n; i+=po) {
            int mid=i+po/2;
            for (int j=0; j<n; j++) {
                s[j]='0';
                if (j>=i && j<i+po) s[j]='1';
            }
            for (int j=i; j<mid; j++) {
                s[j]='0';
                add_element(s);
                s[j]='1';
            }
        }
        po/=2;
    }
    compile_set(), po=x;
    while(po>1) {
        for (int i=0; i<n; i+=po) {
            for (int j=0; j<n; j++) {
                s[j]='0';
                if (dp[j]==i) s[j]='1';
            }
            for (int j=0; j<n; j++) {
                if (dp[j]==i) {
                    s[j]='0';
                    bool f=check_element(s);
                    s[j]='1';
                    if (!f) dp[j]+=po/2;
                }
            }
        }
        po/=2;
    }
    return dp;
}

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