Submission #961254

#	Time	Username	Problem	Language	Result	Execution time	Memory
961254		Ahmed57	Unscrambling a Messy Bug (IOI16_messy)	C++17	38 / 100	2 ms	512 KiB

messy

#include <bits/stdc++.h>
#include "messy.h"

using namespace std;
/*
vector<int> p;
map<string,int> mp;
void add_element(string s){
    string v;
    for(int i = 0;i<s.size();i++){
        v+='0';
    }
    for(int i = 0;i<p.size();i++){
        v[i] = s[p[i]];
    }
    mp[v] = 1;
}
int check_element(string s){
    return mp[s];
}*/
string build(vector<int> x,int n){
    string s;
    for(int i = 0;i<n;i++)s+='0';
    for(auto i:x)s[i] = '1';
    return s;
}
/*
void compile_set(){
    return ;
}*/
vector<int> restore_permutation(int n, int w, int r){
    add_element(build({0},n));
    add_element(build({2},n));
    for(int i = 1;i<n;i*=2){
        for(int j = 0;j<n;j+=2*i){
            vector<int> nah,nah2;
            for(int e = j;e<j+2*i;e++){
                nah.push_back(e);
            }
            for(int e = j+i-1;e<j+2*i;e++){
                nah2.push_back(e);
            }
            add_element(build(nah,n));
            if(i==1){
                add_element(build({j,0,2},n));
                continue;
            }
            add_element(build(nah2,n));
        }
    }
    compile_set();
    vector<vector<int>> comps;
    vector<int> ind;
    for(int i = 0;i<n;i++){
        if(check_element(build({i},n))){
            ind.push_back(i);
        }
        comps.push_back({i});
    }
    while(comps.size()!=1){
        vector<vector<int>> ncomps;
        for(int i = 0;i<comps.size();i++){
            for(int j = i+1;j<comps.size();j++){
                vector<int> comb,comb2,rev;
                for(auto e:comps[i])comb.push_back(e);
                for(auto e:comps[j])comb.push_back(e);
                for(auto e:comps[j])rev.push_back(e);
                for(auto e:comps[i])rev.push_back(e);
                for(auto e:comps[i])comb2.push_back(e);
                comb2.push_back(comps[j].back());
                if(check_element(build(comb,n))==0)continue;
                if(comps.size()==n){
                    ncomps.push_back(comb);
                }else{
                    if(check_element(build(comb2,n))){
                        ncomps.push_back(rev);
                    }else ncomps.push_back(comb);
                }
            }
        }
        if(comps.size()==n){
            for(int j = 0;j<ncomps.size();j++){
                if(check_element(build({ncomps[j][1],ind[0],ind[1]},n))){
                    swap(ncomps[j][0],ncomps[j][1]);
                }
            }
        }
        comps = ncomps;
    }
    vector<int> perm(n);
    for(int j = 0;j<comps[0].size();j++){
        perm[comps[0][j]] = j;
    }
    return perm;
}/*
int main(){
    int n;cin>>n;
    for(int i = 0;i<n;i++){
        int x;cin>>x;
        p.push_back(x);
    }
    vector<int> lol = restore_permutation(n,0,0);
    for(auto i:lol)cout<<i<<" ";
}*/

Compilation message (stderr)

messy.cpp: In function 'std::vector<int> restore_permutation(int, int, int)':
messy.cpp:62:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         for(int i = 0;i<comps.size();i++){
      |                       ~^~~~~~~~~~~~~
messy.cpp:63:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |             for(int j = i+1;j<comps.size();j++){
      |                             ~^~~~~~~~~~~~~
messy.cpp:72:32: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |                 if(comps.size()==n){
      |                    ~~~~~~~~~~~~^~~
messy.cpp:81:24: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   81 |         if(comps.size()==n){
      |            ~~~~~~~~~~~~^~~
messy.cpp:82:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |             for(int j = 0;j<ncomps.size();j++){
      |                           ~^~~~~~~~~~~~~~
messy.cpp:91:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for(int j = 0;j<comps[0].size();j++){
      |                   ~^~~~~~~~~~~~~~~~

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