Submission #302752

#	Time	Username	Problem	Language	Result	Execution time	Memory
302752		dantoh000	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	3 ms	544 KiB

messy

#include <bits/stdc++.h>
using namespace std;
#include "messy.h"
///dont forget about out of bounds errors :/
vector<int> ret;
int n;
void query(int s, int e){
    if (s == e) return;
    string Q;
    int m = (s+e)/2;
    for (int i = 0; i < n; i++){
        if (s <= i && i <= e) Q += "0";
        else Q += "1";
    }
    for (int i = s; i <= m; i++){
        Q[i] = '1';
        add_element(Q);
        Q[i] = '0';
    }
    query(s,m);
    query(m+1,e);
}
void solve(int s, int e, vector<int> q){
    if (s == e){
        ret[q[0]] = s;
        return;
    }
    string Q;
    for (int i=0 ; i < n; i++) Q+="0";
    int ct = 0;
    for (int i = 0; i < n; i++){
        if (ct < q.size() && q[ct] == i){
            ct++;
        }
        else{
            Q[i] = '1';
        }
    }
    vector<int> Lq, Rq;
    for (auto x : q){
        Q[x] = '1';
        if (check_element(Q)) Lq.emplace_back(x);
        else Rq.emplace_back(x);
        Q[x] = '0';
    }
    int m = (s+e)/2;
    solve(s,m, Lq);
    solve(m+1,e, Rq);
}
vector<int> restore_permutation(int N, int w, int r) {
    n = N;
    ret.resize(n);
    query(0,n-1);
    compile_set();
    vector<int> qinit;
    qinit.resize(n);
    iota(qinit.begin(),qinit.end(),0);
    solve(0,n-1,qinit);
    return ret;
}

Compilation message (stderr)

messy.cpp: In function 'void solve(int, int, std::vector<int>)':
messy.cpp:32:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         if (ct < q.size() && q[ct] == i){
      |             ~~~^~~~~~~~~~

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