Submission #777256

#	Time	Username	Problem	Language	Result	Execution time	Memory
777256		tigar	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	2 ms	560 KiB

messy

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

using namespace std;

map<int, int>permutation;

vector<string> adding(int n)
{
    vector<string>ans;
    if(n==0)return ans;
    string s, s1;
    for(int i=0; i<n; i++)s+='0';
    for(int i=0; i<n/2; i++){s[i]='1'; ans.push_back(s); s[i]='0'; s1+='1';}
    vector<string>p=adding(n/2);
    for(int i=0; i<p.size(); i++){ans.push_back(p[i]+s1); ans.push_back(s1+p[i]);}
    return ans;
}

void reading(int l, int r, vector<int>possible, int n)
{
    vector<int>ans1, ans2;
    if(l==r+1)
    {
        string s;
        for(int i=0; i<n; i++)
        {
            if(i==possible[1])s+='0';
            else s+='1';
        }
        if(check_element(s)){permutation[possible[0]]=l; permutation[possible[1]]=r;}
        else {permutation[possible[1]]=l; permutation[possible[0]]=r;}
        return;
    }
    if(l==r)
    {
        permutation[possible[0]]=l; return;
    }
    string s;
    for(int i=0; i<n; i++)s+='1';
    for(int i=0; i<possible.size(); i++)s[possible[i]]='0';
    for(int i=0; i<possible.size(); i++)
    {
        s[possible[i]]='1';
        if(check_element(s))ans1.push_back(possible[i]);
        else ans2.push_back(possible[i]);
        s[possible[i]]='0';
    }
    reading(l, (l+r)/2, ans1, n);
    reading((r+l)/2+1, r, ans2, n);
    return;
}

std::vector<int>
//void
restore_permutation(int n, int w, int r)
{
    vector<string>a=adding(n);
    for(int i=0; i<a.size(); i++)add_element(a[i]);
    compile_set();
    vector<int>b;
    for(int i=0; i<n; i++)b.push_back(i);
    reading(0, n-1, b, n);
    vector<int>ans;
    for(int i=0; i<n; i++)ans.push_back(permutation[i]);
    return ans;
}

/*int main()
{
    int n, w, r;
    cin>>n>>w>>r;
    restore_permutation(n, w, r);
}*/

Compilation message (stderr)

messy.cpp: In function 'std::vector<std::__cxx11::basic_string<char> > adding(int)':
messy.cpp:16:19: 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]
   16 |     for(int i=0; i<p.size(); i++){ans.push_back(p[i]+s1); ans.push_back(s1+p[i]);}
      |                  ~^~~~~~~~~
messy.cpp: In function 'void reading(int, int, std::vector<int>, int)':
messy.cpp:41:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(int i=0; i<possible.size(); i++)s[possible[i]]='0';
      |                  ~^~~~~~~~~~~~~~~~
messy.cpp:42:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i=0; i<possible.size(); i++)
      |                  ~^~~~~~~~~~~~~~~~
messy.cpp: In function 'std::vector<int> restore_permutation(int, int, int)':
messy.cpp:59:19: 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]
   59 |     for(int i=0; i<a.size(); i++)add_element(a[i]);
      |                  ~^~~~~~~~~

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