Submission #63656

#	Time	Username	Problem	Language	Result	Execution time	Memory
63656		KHUSRAV	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	4 ms	512 KiB

messy

#include "messy.h"
#include<bits/stdc++.h>
using namespace std ;
vector<int> ans;
string g ;
void Adder(string x , long long l , long long r){
    long long m = (l + r) / 2 ;
    for(int j = l ; j <= m ; j++){
        x[j] = '1';
        add_element(x);
        x[j] = '0';
    }
    if(l + 1 == r)
        return ;
    for(int j = l ; j <= m ; j++)
        x[j] = '1';
    Adder(x , m + 1 , r);
    for(int j = l ; j <= m ; j++)
        x[j] = '0';

    for(int j = m + 1; j <= r ; j++)
        x[j] = '1';

    Adder(x , l , m);

}
void Go_get_ans(vector<long long> v , long long l , long long r){
    vector<long long> x , y;

    if(v.size() == 0)
        return;
    string s = g ;
    for(int i = 0 ; i < v.size() ; i++)
        s[v[i]] = '0';
    for(int i = 0 ; i < v.size() ; i++){
        s[v[i]] = '1';
        if(check_element(s))
            x.push_back(v[i]);
        else y.push_back(v[i]);
        s[v[i]] = '0';
    }
    if(x.size() == 1){
        ans[x[0]] = l;
        ans[y[0]] = r;
    }
    else{
        Go_get_ans(x , l , (l + r) / 2);
        Go_get_ans(y , (l + r) / 2 + 1 , r);
    }
}
vector<int> restore_permutation(int n, int w, int r) {
    string s = "";
    for(int i = 1 ; i <= n ; i++){
        s += '0';
        g += '1';
    }

    Adder(s , 0 , n - 1);
    compile_set();

    for(int i = 0 ; i < n ; i++)
        ans.push_back(0);
    vector<long long> t;

    for(int i = 0 ; i < n ; i++)
        t.push_back(i);
    Go_get_ans(t , 0 , n - 1);

    return ans;
}

Compilation message (stderr)

messy.cpp: In function 'void Go_get_ans(std::vector<long long int>, long long int, long long int)':
messy.cpp:33:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0 ; i < v.size() ; i++)
                     ~~^~~~~~~~~~
messy.cpp:35:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int 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