Submission #1005699

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005699		hasan2006	Unscrambling a Messy Bug (IOI16_messy)	C++17	100 / 100	1 ms	632 KiB

messy

#include <bits/stdc++.h>
#include "messy.h"

using namespace std;

#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define se second
#define fi first
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"

int n , a[200];

void rec(int l , int r){
    if(r - l == 1)
        return;
    string a(n , '0');
    for(int i = l; i < r; i++)
        a[i] = '1';
    for(int i = l; i < (l + r) / 2; i++){
        a[i] = '0';
        add_element(a);
        a[i] = '1';
    }
    rec(l , (l + r) / 2);
    rec((l + r) / 2 , r);
}

void f(vector<int>v , int x){
    if(v.size() == 1){
        a[v[0]] = x;
        return;
    }
    string s(n , '0');
    vector<int>l , r;
    for(auto to : v)
        s[to] = '1';
    for(auto to : v){
        s[to] = '0';
        if(check_element(s))
            l.pb(to);
        else
            r.pb(to);
        s[to] = '1';
    }
    f(l , x);
    f(r , x | r.size());
}

vector<int> restore_permutation(int n, int w, int r) {
    vector<int>v , ans;
    int i;
    ::n = n;
    rec(0, n);
    compile_set();
    for(i = 0; i < n; i++)
        v.pb(i);
    f(v , 0);
    for(i = 0; i < n; i++)
        ans.pb(a[i]);
    return ans;
}

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