Submission #217956

#	Time	Username	Problem	Language	Result	Execution time	Memory
217956		emil_physmath	Unscrambling a Messy Bug (IOI16_messy)	C++17	70 / 100	15 ms	640 KiB

messy

#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include "messy.h"
using namespace std;
const int bits = 7;
const int maxN = 1 << bits;

int p[maxN];

map<string, bool> cache;
bool Query(const string& a)
{
    auto it = cache.find(a);
    if (it != cache.end())
        return it->second;
    return cache[a] = check_element(a);
}
vector<int> restore_permutation(int n, int w, int r) {
    add_element("0" + string(n - 1, '1'));
    add_element("00" + string(n - 2, '1'));
    add_element("000" + string(n - 3, '1'));
    for (int i = 3; i < n; ++i)
        for (int x = 0; x < bits; ++x)
            if (i & (1 << x))
            {
                string s(n, '0');
                for (int y = 0; y < 3; ++y) // COSTANT
                    if ((x + 1) & (1 << y))
                        s[y] = '1';
                s[i] = '1';
                add_element(s);
            }
    compile_set();
    for (int i = 0; i < 3; ++i)
        for (int j = 0; j < n; ++j)
        {
            string s = string(n, '1');
            for (int k = 0; k < i; ++k)
                s[p[k]] = '0';
            s[j] = '0';
            if (count(s.begin(), s.end(), '0') != i + 1) continue;
            if (Query(s))
            {
                p[i] = j;
                break;
            }
        }
    for (int i = 3; i < n; ++i)
        for (int j = 0; j < n; ++j)
        {
            if (j == p[0] || j == p[1] || j == p[2]) continue;
            bool f = true;
            for (int x = 0; x < bits; ++x)
                if (i & (1 << x))
                {
                    string s(n, '0');
                    for (int y = 0; y < 3; ++y) // COSTANT
                        if ((x + 1) & (1 << y))
                            s[p[y]] = '1';
                    s[j] = '1';
                    if (!Query(s))
                    {
                        f = false;
                        break;
                    }
                }
                else
                {
                    string s(n, '0');
                    for (int y = 0; y < 3; ++y) // COSTANT
                        if ((x + 1) & (1 << y))
                            s[p[y]] = '1';
                    s[j] = '1';
                    if (Query(s))
                    {
                        f = false;
                        break;
                    }
                }
            if (f)
                p[i] = j;
        }
    vector<int> res(n);
    for (int i = 0; i < n; ++i)
        res[p[i]] = i;
    return res;
}

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