Submission #125300

#	Time	Username	Problem	Language	Result	Execution time	Memory
125300		turbat	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	5 ms	632 KiB

messy

#include <bits/stdc++.h>
#include "messy.h"
using namespace std;

int n;
vector <int> ans;

void add(int l, int r){
	if (l == r) return;
	string st = "";
	for (int i = 0;i < n;i++){
		if (i < l || r < i) st += '1';
		else st += '0';
	}
	int mid = (l + r) / 2;
	for (int i = l;i <= mid;i++){
		st[i] = '1';
		add_element(st);
		st[i] = '0';
	}
	add (l , mid);
	add(mid + 1, r);
}

void solve (int l, int r, vector <int> v){
	// cout << l << ' ' << r << endl;
	// for (int i : v) cout << i << " ";
	// cout << endl;
	if (l == r){
		sort(v.begin(), v.end());
		for (int i = 0;i < v.size();i++)
			if (i != v[i]){
				// cout << l << i << ' ';
				ans.push_back(i);
				return;
			}
		// cout << l << n - 1 << ' ';
		ans.push_back(n - 1);
		return;
	}
	vector <int> v1 = v, v2 = v;
	string st = "";
	for (int i = 0;i < n;i++) st += '0';
	for (int x : v) st[x] = '1';
	for (int i = 0;i < n;i++)
		if (st[i] == '0'){
			st[i] = '1';
			if (check_element(st)) v2.push_back(i);
			else v1.push_back(i);
			st[i] = '0';
		}
	int mid = (l + r) / 2;
	solve (l, mid, v1);
	solve (mid + 1, r, v2);
}

vector<int> restore_permutation(int n, int w, int r) {
	:: n = n;	
	add(0, n - 1);
	compile_set();
	vector <int> v;
	// cout <<"########################\n";
	solve (0, n - 1, v);
	// cout << endl;
	// for (int i : ans) cout << i << ' ';
	vector <int> ve(n);
	for (int i = 0;i < n;i++) ve[ans[i]] = i;
    return ve;
}

Compilation message (stderr)

messy.cpp: In function 'void solve(int, int, std::vector<int>)':
messy.cpp:31:20: 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