Submission #241723

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

messy

#include <bits/stdc++.h>
#include "messy.h"
 
using namespace std;
 
 
string x;
vector <int> sol;
 
void solve (int st , int dr , vector <int> now){ /// returneaza ordinea din intervalul st ... dr
    int mid = (st + dr)/2 , i;
    vector <int> l , r;
 
    if (st == dr){
 
        //printf ("%d %d\n", now[0] , st);
        sol[now[0]] = st;
 
        return;
    }
    for (i = 0 ; i < (dr - st + 1) ; i++){
 
        x[now[i]] = '1';
 
        if (check_element(x))
            l.push_back(now[i]);
        else r.push_back(now[i]);
 
        x[now[i]] = '0';
 
    }
 
    /// elementele din l sunt in setul din stanga, cele din r in setul din dreapta
 
 
    for (i = 0 ; i < l.size() ; i++)
        x[l[i]] = '1';
 
    solve(mid + 1 , dr , r);
 
    for (i = 0 ; i < l.size() ; i++)
        x[l[i]] = '0';
 
    /// --------------------------------
 
    for (i = 0 ; i < r.size() ; i++)
        x[r[i]] = '1';
 
    solve(st , mid , l);
 
    for (i = 0 ; i < r.size() ; i++)
        x[r[i]] = '0';
 
 
}
 
void inser (int st , int dr){
    int mid = (st + dr) / 2 , i;
 
    if (st == dr)
        return;
 
    for (i = 0 ; i < (dr - st + 1) / 2 ; i++){
 
        x[i + st] = '1';
 
        add_element(x);
        x[i + st] = '0';
 
    }
 
 
    for (i = st ; i <= mid ; i++)
        x[i] = '1';
 
    inser(mid + 1 , dr);
 
    for (i = st ; i <= mid ; i++)
        x[i] = '0';
 
    /// --------------------------------
 
    for (i = mid + 1 ; i <= dr ; i++)
        x[i] = '1';
 
    inser(st , mid);
 
    for (i = mid + 1 ; i <= dr ; i++)
        x[i] = '0';
 
}
 
vector<int> restore_permutation(int n, int w, int r) {
    int i;
    /// setul de inserat e constant
    vector <int> now;
 
    x.resize(n , '0');
 
    for (i = 0 ; i < n / 2 ; i++){
        x[i] = '1';
        add_element(x);
        x[i] = '0';
    }
 
    inser (0 , n - 1);
 
    compile_set();
 
    for (i = 0 ; i < n ; i++)
        now.push_back(i);
 
    sol.resize(n , 0);
 
    solve (0 , n - 1 , now);
 
    return sol;
}

Compilation message (stderr)

messy.cpp: In function 'void solve(int, int, std::vector<int>)':
messy.cpp:36:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0 ; i < l.size() ; i++)
                  ~~^~~~~~~~~~
messy.cpp:41:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0 ; i < l.size() ; i++)
                  ~~^~~~~~~~~~
messy.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0 ; i < r.size() ; i++)
                  ~~^~~~~~~~~~
messy.cpp:51:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0 ; i < r.size() ; i++)
                  ~~^~~~~~~~~~

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