Submission #1067204

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067204		andrei_iorgulescu	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	3 ms	856 KiB

messy

#include <bits/stdc++.h>
#include "messy.h"
#warning That's not FB, that's my FB

using namespace std;

int N;

string make_query(vector<int> where_1)
{
    string lol;
    for (int i = 0; i < N; i++)
        lol.push_back('0');
    for (auto it : where_1)
        lol[it] = '1';
    return lol;
}

vector<int> restore_permutation(int n, int w, int r)
{
    N = n;
    int k = __lg(n);
    int pas = 0;
    for (int iter = 2; iter <= n; iter *= 2)
    {
        pas++;
        if (iter == 2)
        {
            for (int i = 0; i < (1 << (k - 1)); i++)
            {
                vector<int> where_1 = {i};
                string tq = make_query(where_1);
                //cout << tq << endl;
                add_element(tq);
            }
        }
        else
        {
            for (int i = 0; i < n; i += (1 << (k + 1 - pas)))
            {
                vector<int> where_1;
                for (int j = i + (1 << (k - pas + 1)); j < i + (1 << (k + 1 - pas)) + (1 << (k - pas + 1)); j++)
                    where_1.push_back(j % n);
                for (int j = i; j < i + (1 << (k - pas)); j++)
                {
                    where_1.push_back(j);
                    string tq = make_query(where_1);
                    //cout << tq << endl;
                    add_element(tq);
                    where_1.pop_back();
                }
            }
        }
    }
    compile_set();
    vector<vector<int>> seturi;
    seturi.push_back({});
    for (int i = 0; i < n; i++)
        seturi[0].push_back(i);
    pas = 0;
    for (int iter = 2; iter <= n; iter *= 2)
    {
        pas++;
        vector<vector<int>> new_seturi;
        if (iter == 2)
        {
            vector<int> v0, v1;
            for (int i = 0; i < n; i++)
            {
                vector<int> where_1 = {i};
                string tq = make_query(where_1);
                bool bb = check_element(tq);
                if (bb)
                    v0.push_back(i);
                else
                    v1.push_back(i);
            }
            new_seturi.push_back(v0);
            new_seturi.push_back(v1);
        }
        else
        {
            for (int i = 0; i < seturi.size(); i++)
            {
                vector<int> v0, v1;
                for (auto it : seturi[i])
                {
                    vector<int> where_1 = {it};
                    for (auto itt : seturi[(i + 1) % (int)seturi.size()])
                        where_1.push_back(itt);
                    string tq = make_query(where_1);
                    //cout << tq << endl;
                    bool bb = check_element(tq);
                    if (bb)
                        v0.push_back(it);
                    else
                        v1.push_back(it);
                }
                new_seturi.push_back(v0);
                new_seturi.push_back(v1);
            }
        }
        seturi = new_seturi;
    }
    vector<int> pos(n), p(n);
    for (int i = 0; i < n; i++)
        pos[i] = seturi[i][0], p[pos[i]] = i;
    return p;
}

Compilation message (stderr)

messy.cpp:3:2: warning: #warning That's not FB, that's my FB [-Wcpp]
    3 | #warning That's not FB, that's my FB
      |  ^~~~~~~
messy.cpp: In function 'std::vector<int> restore_permutation(int, int, int)':
messy.cpp:83:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |             for (int i = 0; i < seturi.size(); i++)
      |                             ~~^~~~~~~~~~~~~~~

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