Submission #95554

#	Time	Username	Problem	Language	Result	Execution time	Memory
95554		hihi	Unscrambling a Messy Bug (IOI16_messy)	C++11	100 / 100	7 ms	616 KiB

messy

#include "messy.h"
#include <bits/stdc++.h>
using namespace std;
int N;
vector<int> ans;
void addStuff(int start, int stop, int flagStart, int flagStop) {
    for (int i=start;i<(start+stop)/2;i++) {
        string s = "";
        for (int j=0;j<N;j++) {
            if (j == i || (flagStart <= j && j < flagStop)) {
                s += "1";
            } else {
                s += "0";
            }
        }
        add_element(s);
    }
    if (stop - start > 2) {
        addStuff(start, (start+stop)/2, (start+stop)/2, stop);
        addStuff((start+stop)/2, stop, start, (start+stop)/2);
    }
}
void checkStuff(int start, int stop, vector<int>& flags, vector<int>& candidates) {
    vector<int> zeroFlags, oneFlags;
    string s = "";
    for (int i=0;i<N;i++) s += "0";
    for (int i=0;i<flags.size();i++) s[flags[i]] = '1';
    for (int i=0;i<candidates.size();i++) {
        string q = s;
        q[candidates[i]] = '1';
        if (check_element(q)) {
            oneFlags.push_back(candidates[i]);
        } else {
            zeroFlags.push_back(candidates[i]);
        }
    }
    if (stop - start > 2) {
        checkStuff(start, (start+stop)/2, zeroFlags, oneFlags);
        checkStuff((start+stop)/2, stop, oneFlags, zeroFlags);
    } else {
        ans[oneFlags[0]] = start;
        ans[zeroFlags[0]] = start + 1;
    }
}


vector<int> restore_permutation(int _n, int w, int r) {
    N = _n;
    addStuff(0, N, -1, -1);
    compile_set();
    ans.resize(N);
    vector<int> x;
    vector<int> all;
    all.resize(N);
    for (int i=0;i<N;i++) all[i] = i;
    checkStuff(0, N, x, all);
    return ans;
}

Compilation message (stderr)

messy.cpp: In function 'void checkStuff(int, int, std::vector<int>&, std::vector<int>&)':
messy.cpp:27:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<flags.size();i++) s[flags[i]] = '1';
                  ~^~~~~~~~~~~~~
messy.cpp:28:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<candidates.size();i++) {
                  ~^~~~~~~~~~~~~~~~~~

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