Submission #239832

#	Time	Username	Problem	Language	Result	Execution time	Memory
239832		Ruxandra985	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