Submission #1176017

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

messy

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

using namespace std;

const int maxn = 200;
int pp[maxn];
int N;
int outside[maxn];
void ask(int l, int r)
{
    if(l == r)
    {
        return;
    }
    memset(outside, 0, sizeof(outside));

    int mid = (l + r)/ 2;
    /// in first half
    vector < int > addon;
    for (int i = l; i <= mid; ++ i)
        addon.push_back(i);

    for (int i = 0; i < l; ++ i)
        outside[i] = 1;
    for (int i = r+1; i < N; ++ i)
        outside[i] = 1;

    for (auto x: addon)
    {
        string askme = "";
        for (int i = 0; i < N; ++ i)
        {
            if(i == x || outside[i])askme += '1';
            else askme += '0';
        }
        add_element(askme);
       /// cout << askme << endl;
    }
    ask(l, mid);
    ask(mid+1, r);

}
int outrange[maxn];
int inrange[maxn];
void solve(int l, int r, vector < int > g)
{
    /*cout << l << " " << r << endl;
    for (auto val: g)
        cout << val << " ";
    cout << endl;*/
    if(l == r)
    {
        pp[g[0]] = l;
        return;
    }
    int mid = (l + r)/2;
    memset(inrange, 0, sizeof(inrange));
    memset(outrange, 0, sizeof(outrange));
    for (auto x: g)
    {
        inrange[x] = 1;
    }
    for (int i = 0; i < N; ++ i)
    {
        if(!inrange[i])outrange[i] = 1;
    }
    vector < int > onleft, onright;
    for (auto x: g)
    {
        string tryme = "";
        for (int i = 0; i < N; ++ i)
            if(i == x || outrange[i])tryme += '1';
        else tryme += '0';
        ///cout << tryme << endl;

        if(check_element(tryme))
        {
            onleft.push_back(x);
            ///cout << "goes left" << endl;
        }
        else
        {
            onright.push_back(x);
            ///cout << "goes right" << endl;
        }
    }
    solve(l, mid, onleft);
    solve(mid+1, r, onright);

}
std::vector<int> restore_permutation(int n, int w, int r)
{
    N = n;
   /// cout << "asking " << endl;
    ask(0, N-1);
   /// cout << "answering " << endl;
    compile_set();
    vector < int > g;
    for (int i = 0; i < n; ++ i)
        g.push_back(i);
    solve(0, N-1, g);
    vector < int > ans;
    for (int i = 0; i < n; ++ i)
        ans.push_back(pp[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