Submission #1137646

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

messy

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

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const int N = 1024;
int wh[N];
string curq;

inline void S(int p, int k, char z)
{
    for(int i = p; i <= k; ++i)
        curq[i] = z;
}

void DoQ(int p, int k)
{
    if(p == k) return;
    int s = (p + k) / 2;
    for(int i = p; i <= s; ++i)
    {
        curq[i] = '1';
        add_element(curq);
        curq[i] = '0';
    }
    S(s + 1, k, '1');
    DoQ(p, s);
    S(s + 1, k, '0');
    S(p, s, '1');
    DoQ(s + 1, k);
    S(p, s, '0');
}

void S2(vector<int> &v, char z)
{
    for(int i = 0; i < (int)v.size(); ++i)
        curq[v[i]] = z;
}

void Rev(int p, int k, vector<int> pos)
{
    if(p == k)
    {
        wh[p] = pos[0];
        return;
    }
    vector<int> l, r;
    int s = (p + k) / 2;
    for(int i = 0; i < (int)pos.size(); ++i)
    {
        curq[pos[i]] = '1';
        if(check_element(curq))
            l.pb(pos[i]);
        else
            r.pb(pos[i]);
        curq[pos[i]] = '0';
    }
    pos.clear();
    S2(r, '1');
    Rev(p, s, l);
    S2(r, '0');
    S2(l, '1');
    Rev(s + 1, k, r);
    S2(l, '0');
}

vector<int> restore_permutation(int _n, int _w, int _r)
{
    int n = _n;
    vector<int> ans(n, 0), pos;
    for(int i = 0; i < n; ++i)
    {
        pos.pb(i);
        curq.pb('0');
    }
    DoQ(0, n - 1);
    compile_set();
    Rev(0, n - 1, pos);
    for(int i = 0; i < n; ++i)
        ans[wh[i]] = i;
    return ans;
}

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