Submission #743031

#	Time	Username	Problem	Language	Result	Execution time	Memory
743031		boris_mihov	Unscrambling a Messy Bug (IOI16_messy)	C++17	41 / 100	2 ms	564 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 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';
                }
            }
        }

        compile_set();
        std::fill(element.begin(), element.end(), '1');
        std::fill(posOf, posOf + n, 0);

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

            element[i] = '1';
        }

        for (int i = 0 ; (1 << i) < n ; ++i)
        {
            for (int j = 0 ; j < n ; ++j)
            {
                if (element[j] == '0')
                {
                    continue;
                }

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

                element[j] = '1';
            }
        }

        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[i] == '1')
                {
                    continue;
                }

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

                element[i] = '0';
            }
        }

        int log = 0;
        std::bitset <MAXN> curr2;
        for (int bit = 0 ; (1 << bit) < n ; ++bit)
        {
            log++;
            curr2 |= bs[bit];
        }

        assert(curr2.count() == n - log - 1);
        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] != 0)
            {
                break;
            }

            std::bitset <MAXN> curr;
            for (int i = 0 ; i < n ; ++i)
            {
                curr[i] = 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:47:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |             for (int j = 0 ; j < zeroPos.size() - 1 ; ++j)
      |                              ~~^~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from messy.cpp:5:
messy.cpp:158:30: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  158 |         assert(curr2.count() == n - log - 1);
      |                ~~~~~~~~~~~~~~^~~~~~~~~~~~~~

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