Submission #952559

#	Time	Username	Problem	Language	Result	Execution time	Memory
952559		SmuggingSpun	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	2 ms	616 KiB

messy

#include "messy.h"
#include<bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
vector<int>restore_permutation(int n, int w, int r){
	if(n <= 32 && (r << 1) >= n * n){
		string s(n, '0'), current(n, '0');
		for(int i = 0; i + 1 < n; i++){
			s[i] = '1';
			add_element(s);
		}
		compile_set();
		vector<int>ans(n), p(n);
		iota(p.begin(), p.end(), 0);
		for(int i = 0; i < n; i++){
			shuffle(p.begin(), p.end(), rng);
			int index = int(p.size()) - 1;
			for(int i = 0; i + 1 < p.size(); i++){
				current[p[i]] = '1';
				if(check_element(current)){
					index = i;
					break;
				}
				current[p[i]] = '0';
			}
			current[p[index]] = '1';
			ans[p[index]] = i;
			p.erase(p.begin() + index);
		}
		return ans;
	}
	function<void(int, int, vector<int>)>add;
	add = [&] (int l, int r, vector<int>must_1){
		if(l == r){
			return;
		}	
		int m = (l + r) >> 1;
		string s(n, '0');
		for(int& x : must_1){
			s[x] = '1';
		}
		for(int i = l; i <= m; i++){
			s[i] = '1';
			add_element(s);
			s[i] = '0';
			must_1.emplace_back(i);
		}
		add(m + 1, r, must_1);
		for(int i = l; i <= m; i++){
			must_1.pop_back();
		}
		for(int i = m + 1; i <= r; i++){
			must_1.emplace_back(i);
		}
		add(l, m, must_1);
	};
	add(0, n - 1, vector<int>());
	compile_set();
	vector<int>ans(n);
	function<void(int, int, vector<int>, vector<int>)>solve;
	solve = [&] (int l, int r, vector<int>index, vector<int>must_1){
		if(l == r){
			ans[index[0]] = l;
			return;
		}
		string s(n, '0');
		for(int& x : must_1){
			s[x] = '1';
		}
		int m = (l + r) >> 1;
		vector<int>left, right;
		for(int i = 0; i < index.size(); i++){
			s[index[i]] = '1';
			if(check_element(s)){
				left.emplace_back(index[i]);
			}
			else{
				right.emplace_back(index[i]);
			}
			s[index[i]] = '0';
		}
		for(int& x : left){
			must_1.emplace_back(x);
		}
		solve(m + 1, r, right, must_1);
		for(int i = 0; i < left.size(); i++){
			must_1.pop_back();
		}
		for(int& x : right){
			must_1.emplace_back(x);
		}
		solve(l, m, left, must_1);
	};
	vector<int>index(n);
	iota(index.begin(), index.end(), 0);
	solve(0, n - 1, index, vector<int>());
	return ans;
}

Compilation message (stderr)

messy.cpp: In function 'std::vector<int> restore_permutation(int, int, int)':
messy.cpp:18:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |    for(int i = 0; i + 1 < p.size(); i++){
      |                   ~~~~~~^~~~~~~~~~
messy.cpp: In lambda function:
messy.cpp:72:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   for(int i = 0; i < index.size(); i++){
      |                  ~~^~~~~~~~~~~~~~
messy.cpp:86:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |   for(int i = 0; i < left.size(); i++){
      |                  ~~^~~~~~~~~~~~~

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