Submission #742937

#	Time	Username	Problem	Language	Result	Execution time	Memory
742937		boris_mihov	Unscrambling a Messy Bug (IOI16_messy)	C++17	38 / 100	1 ms	340 KiB

messy

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

typedef long long llong;
const int MAXN = 128;
const int INF  = 1e9;

std::vector <int> perm;
std::vector <int> restore_permutation(int n, int w, int r) 
{
    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;
        }
    }

    return perm;
}

Compilation message (stderr)

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

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