Submission #1225488

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225488		Hamed_Ghaffari	Unscrambling a Messy Bug (IOI16_messy)	C++20	100 / 100	1 ms	584 KiB

messy

#include <vector>
#include "messy.h"
#include <bits/stdc++.h>
using namespace std;

#define mid ((l+r)>>1)

int n;
vector<int> p;
string s;

void add(int l, int r) {
    if(r-l==1) return;
    for(int i=l; i<mid; i++) {
        s[i] = '1';
        add_element(s);
        s[i] = '0';
    }
    for(int i=mid; i<r; i++) s[i] = '1';
    add(l, mid);
    for(int i=l; i<mid; i++) s[i] = '1';
    for(int i=mid; i<r; i++) s[i] = '0';
    add(mid, r);
    for(int i=l; i<mid; i++) s[i] = '0';
}

void check(int l, int r, vector<int> vec) {
    if(r-l==1) {
        p[vec[0]] = l;
        return;
    }
    vector<int> vecl, vecr;
    for(int i : vec) {
        s[i] = '1';
        (check_element(s) ? vecl : vecr).push_back(i);
        s[i] = '0';
    }
    for(int i : vecr) s[i] = '1';
    check(l, mid, vecl);
    for(int i : vecl) s[i] = '1';
    for(int i : vecr) s[i] = '0';
    check(mid, r, vecr);
    for(int i : vecl) s[i] = '0';
}

vector<int> restore_permutation(int n, int w, int r) {
    ::n = n;
    s = string(n, '0');
    add(0, n);
    s = string(n, '0');
    p = vector<int>(n);
    compile_set();
    vector<int> vec(n);
    iota(vec.begin(), vec.end(), 0);
    check(0, n, vec);
    return p;
}

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: 30 / 30