Submission #272708

#	Time	Username	Problem	Language	Result	Execution time	Memory
272708		stoyan_malinin	Unscrambling a Messy Bug (IOI16_messy)	C++14	0 / 100	2124 ms	524292 KiB

messy

#include "messy.h"
//#include "grader.cpp"

#include <set>
#include <vector>
#include <iostream>

using namespace std;

int getLog(int x)
{
    int ans = 0;
    while((1<<ans)!=x) ans++;

    return ans;
}

void gen(string curr, int n, int ones, int zeros, vector <string> &v, vector <string> &all)
{
    if(curr.size()==n)
    {
        bool fail = true;
        for(int i = 0;i<n;i++)
        {
            if(curr[i]!=curr[0])
            {
                fail = false;
                break;
            }
        }

        all.push_back(curr);
        if(fail==false && v.size()<(1<<n)/4)
        {
            v.push_back(curr);
            add_element(curr);
        }

        //cout << curr << '\n';

        return;
    }

    gen(curr+"0", n, ones, zeros+1, v, all);
    gen(curr+"1", n, ones+1, zeros, v, all);
}

set <string> permSet[15][15];

vector<int> restore_permutation(int n, int w, int r)
{
    int logN = getLog(n);

    vector <string> v, all;
    gen("", n, 0, 0, v, all);

    compile_set();
    //cout << "COMPILED" << '\n';

    vector <int> p;
    for(int i = 0;i<n;i++) p.push_back(i);

    for(int i = 0;i<n;i++)
    {
        for(int j = i;j<n;j++)
        {
            swap(p[i], p[j]);

            for(string s: v)
            {
                string newS;
                for(int x: p) newS += s[x];

                permSet[i][j].insert(newS);
            }

            //cout << i << " " << j << " -> " << permSet[i][j].size() << '\n';

            swap(p[i], p[j]);
        }
    }

    vector <bool> base;
    for(string s: all) base.push_back(check_element(s));//, cout << base.back() << '\n';

    for(int i = 0;i<n;i++)
    {
        for(int j = i;j<n;j++)
        {
            swap(p[i], p[j]);

            bool fail = false;
            for(int k = 0;k<all.size();k++)
            {
                if(base[k]!=permSet[i][j].count(all[k]))
                {
                    fail = true;
                    break;
                }
            }

            if(fail==false)
            {
                //cout << "A de " << i << " " << j << '\n';
                return p;
            }

            swap(p[i], p[j]);
        }
    }

    //cout << "FAK" << '\n';
    return {};
}

Compilation message (stderr)

messy.cpp: In function 'void gen(std::string, int, int, int, std::vector<std::__cxx11::basic_string<char> >&, std::vector<std::__cxx11::basic_string<char> >&)':
messy.cpp:20:19: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   20 |     if(curr.size()==n)
      |        ~~~~~~~~~~~^~~
messy.cpp:33:35: warning: comparison of integer expressions of different signedness: 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   33 |         if(fail==false && v.size()<(1<<n)/4)
      |                           ~~~~~~~~^~~~~~~~~
messy.cpp: In function 'std::vector<int> restore_permutation(int, int, int)':
messy.cpp:93:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |             for(int k = 0;k<all.size();k++)
      |                           ~^~~~~~~~~~~
messy.cpp:52:9: warning: unused variable 'logN' [-Wunused-variable]
   52 |     int logN = getLog(n);
      |         ^~~~

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