Submission #432014

#	Time	Username	Problem	Language	Result	Execution time	Memory
432014		davi_bart	Unscrambling a Messy Bug (IOI16_messy)	C++17	0 / 100	2 ms	588 KiB

messy

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "messy.h"
using namespace std;
#define ll long long
#define fi first
#define se second
#define ld long double
#define pb push_back
int N;
string sum(string &a,string &b){
    string c=a;
    for(int i=0;i<b.size();i++){
        if(b[i]=='1')c[i]='1';
    }
    return c;
}
std::vector<int> restore_permutation(int n, int w, int r){
    N=n;
    for(int i=1;i<N;i*=2){
        for(int j=0;j<N;j+=2*i){
            string x=string(N,'0');
            for(int h=j;h<j+i;h++)x[h]='1';
            //cout<<x<<endl;
            assert(x.size()==N);
            add_element(x);
        }
    }
    compile_set();
    vector<int> v[N+2];

    vector<pair<string,int> > g1,g2;
    for(int i=0;i<N;i++){
        string x=string(N,'0');
        x[i]='1';
            assert(x.size()==N);
        if(check_element(x)){
            v[i].pb(1);
            g1.pb({x,i});
        }else{
            g2.pb({x,i});
        }
    }

    for(int i=2;i<N;i*=2){
        vector<pair<string,int> > g3,g4;
        for(auto [a,b]:g1){
            for(auto [c,d]:g2){
                string k=sum(a,c);
            assert(k.size()==N);
                if(check_element(k)){
                    for(int j=b;j<b+i/2;j++)v[j].pb(i);
                    for(int j=d;j<d+i/2;j++)v[j].pb(i);
                    g3.pb({k,min(b,d)});
                }else{
                    g4.pb({k,min(b,d)});
                }
            }
        }
        g1=g3;
        g2=g4;
    }

    vector<int> ans(N);

    for(int i=0;i<N;i++){
        int cur=0;
        for(int j:v[i])cur+=j;
        ans[i]=N-1-cur;
    }
    //reverse(ans.begin(),ans.end());
    return ans;
}

Compilation message (stderr)

messy.cpp: In function 'std::string sum(std::string&, std::string&)':
messy.cpp:13:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for(int i=0;i<b.size();i++){
      |                 ~^~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from messy.cpp:2:
messy.cpp: In function 'std::vector<int> restore_permutation(int, int, int)':
messy.cpp:25:28: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   25 |             assert(x.size()==N);
      |                    ~~~~~~~~^~~
messy.cpp:36:28: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |             assert(x.size()==N);
      |                    ~~~~~~~~^~~
messy.cpp:50:28: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |             assert(k.size()==N);
      |                    ~~~~~~~~^~~

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