Submission #111535

#	Time	Username	Problem	Language	Result	Execution time	Memory
111535		igzi	Unscrambling a Messy Bug (IOI16_messy)	C++17	100 / 100	10 ms	512 KiB

messy

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

using namespace std;

string s;

void pripremi(int n){
int i,j,k;
for(i=2;i<=n;i*=2){
    for(j=0;j<n;j+=i){
        for(k=j;k<j+i;k++) s[k]='0';
        for(k=j;k<j+i/2;k++){
            s[k]='1';
            add_element(s);
            s[k]='0';
        }
        for(k=j;k<j+i;k++) s[k]='1';
    }
}
}

vector<int> ans;

void resi(int n,int l,int d,vector<int> v){
if(l==d){
    ans[v[0]]=l;
    return;
}
int i;
vector<int> a,b;
for(i=0;i<n;i++) s[i]='1';
for(i=0;i<v.size();i++) s[v[i]]='0';
for(i=0;i<v.size();i++){
    s[v[i]]='1';
    if(check_element(s)) a.push_back(v[i]);
    else b.push_back(v[i]);
    s[v[i]]='0';
}
int m=(l+d)/2;
resi(n,l,m,a);
resi(n,m+1,d,b);
}

std::vector<int> restore_permutation(int n, int w, int r) {
    int i;
    for(i=0;i<n;i++) s+='1';
    pripremi(n);
    compile_set();
    vector<int> v;
    for(i=0;i<n;i++) {v.push_back(i); ans.push_back(0);}
    resi(n,0,n-1,v);
    return ans;
}

Compilation message (stderr)

messy.cpp: In function 'void resi(int, int, int, std::vector<int>)':
messy.cpp:34:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<v.size();i++) s[v[i]]='0';
         ~^~~~~~~~~
messy.cpp:35:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<v.size();i++){
         ~^~~~~~~~~

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