Submission #743119

#	Time	Username	Problem	Language	Result	Execution time	Memory
743119		boris_mihov	Unscrambling a Messy Bug (IOI16_messy)	C++17	20 / 100	2 ms	468 KiB

messy

#include "messy.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <bitset>
#include <random>

typedef long long llong;
const int MAXN = 256;
const int MAXLOG = 8;
const int INF  = 1e9;

int p[MAXN];
int posOf[MAXN];
int sorted[MAXN];
std::vector <int> perm;
std::bitset <MAXN> bs[MAXLOG];
std::vector <int> restore_permutation(int n, int w, int r) 
{
    if (n <= 8)
    {
        perm.resize(n); 
        std::string element(n, '0');
        for (int i = 0 ; i < n ; ++i)
        {
            element[i] = '1';
            add_element(element);
        }

        compile_set();
        std::mt19937 mt(69420);
        std::fill(element.begin(), element.end(), '0');
        for (int i = 0 ; i < n ; ++i)
        {
            std::vector <int> zeroPos;
            for (int j = 0 ; j < n ; ++j)
            {
                if (element[j] == '0')
                {
                    zeroPos.push_back(j);
                }
            }

            bool found = false;
            std::shuffle(zeroPos.begin(), zeroPos.end(), mt);
            for (int j = 0 ; j < zeroPos.size() - 1 ; ++j)
            {
                element[zeroPos[j]] = '1';
                if (check_element(element))
                {
                    perm[zeroPos[j]] = i;
                    found = true;
                    break;
                }

                element[zeroPos[j]] = '0';
            }

            if (!found)
            {
                element[zeroPos.back()] = '1';
                perm[zeroPos.back()] = i;
            }
        }
    } else
    {
        perm.resize(n);
        std::string element(n, '1'); element[0] = '0';
        for (int i = 0 ; (1 << i) < n ; ++i)
        {
            add_element(element);
            element[1 << i] = '0';
        }

        add_element(element);
        std::fill(element.begin(), element.end(), '0'); element[0] = '1';
        for (int bit = 0 ; (1 << bit) < n ; ++bit)
        {
            element[1 << bit] = '1';
            for (int i = (1 << bit) + 1 ; i < n ; ++i)
            {
                if (i & (1 << bit))
                {
                    element[i] = '1';
                    add_element(element);
                    element[i] = '0';
                }
            }
        }

        std::mt19937 mt(69);
        compile_set();
        std::fill(element.begin(), element.end(), '1');
        std::fill(posOf, posOf + n, -1);
        std::iota(p, p + n, 0);
        std::shuffle(p, p + n, mt);

        for (int i = 0 ; i < n ; ++i)
        {
            element[p[i]] = '0';
            if (check_element(element))
            {
                posOf[0] = p[i];
                break;
            }

            element[p[i]] = '1';
        }

        std::iota(p, p + n, 0);
        std::shuffle(p, p + n, mt);
        for (int i = 0 ; (1 << i) < n ; ++i)
        {
            for (int j = 0 ; j < n ; ++j)
            {
                if (element[p[j]] == '0')
                {
                    continue;
                }

                element[p[j]] = '0';
                if (check_element(element))
                {
                    posOf[1 << i] = j;
                    break;  
                }

                element[p[j]] = '1';
            }
        }

        std::iota(p, p + n, 0);
        std::shuffle(p, p + n, mt);
        std::fill(element.begin(), element.end(), '0'); element[posOf[0]] = '1';
        for (int bit = 0 ; (1 << bit) < n ; ++bit)
        {
            bs[bit].reset();
            element[posOf[1 << bit]] = '1';
            for (int i = 0 ; i < n ; ++i)
            {
                if (element[p[i]] == '1')
                {
                    continue;
                }

                element[p[i]] = '1';
                if (check_element(element))
                {
                    bs[bit][p[i]] = 1;
                }

                element[p[i]] = '0';
            }
        }

        std::iota(sorted, sorted + n, 0);
        std::sort(sorted, sorted + n, [&](int x, int y)
        {
            return __builtin_popcount(x) < __builtin_popcount(y);
        });

        for (int i = n - 1 ; i >= 0 ; --i)
        {
            int num = sorted[i];
            if (posOf[num] != -1)
            {
                break;
            }
            
            std::bitset <MAXN> curr;
            for (int j = 0 ; j < n ; ++j)
            {
                curr[j] = 1;
            }

            for (int bit = 0 ; (1 << bit) < n ; ++bit)
            {
                if (num & (1 << bit))
                {
                    curr &= bs[bit];
                }
            }
            
            posOf[num] = curr._Find_first();
            for (int bit = 0 ; (1 << bit) < n ; ++bit)
            {
                if (num & (1 << bit))
                {
                    bs[bit][posOf[num]] = 0;
                }
            }
        }

        for (int i = 0 ; i < n ; ++i)
        {
            perm[posOf[i]] = i;
        }
    }

    return perm;
}

Compilation message (stderr)

messy.cpp: In function 'std::vector<int> restore_permutation(int, int, int)':
messy.cpp:48:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |             for (int j = 0 ; j < zeroPos.size() - 1 ; ++j)
      |                              ~~^~~~~~~~~~~~~~~~~~~~

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