Submission #987144

#	Time	Username	Problem	Language	Result	Execution time	Memory
987144		pcc	Unscrambling a Messy Bug (IOI16_messy)	C++17	100 / 100	3 ms	856 KiB

messy

#include <vector>

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

/*
add_element("0");
compile_set();
check_element("0");
return std::vector<int>();
*/

namespace WRITE{
	void GO(int N){
		int B = __lg(N);
		for(int i = B-1;i>=0;i--){
			for(int j = 0;j<N;j+=(1<<(i+1))){
				string s(N,'0');
				for(int k = 0;k<(1<<(i+1));k++)s[j+k] = '1';
				for(int k = 0;k<(1<<i);k++){
					string tmp = s;
					tmp[j+k] = '0';
					add_element(tmp);
				}
			}
		}
		return;
	}
}

namespace READ{
	int N;
	vector<int> ans;
	pair<vector<int>,vector<int>> calc(vector<int> v){
		vector<int> lv,rv;
		string tmp(N,'0');
		for(auto &i:v)tmp[i] = '1';
		for(auto &i:v){
			tmp[i] = '0';
			if(check_element(tmp))lv.push_back(i);
			else rv.push_back(i);
			tmp[i] = '1';
		}
		assert(lv.size() == rv.size());
		return make_pair(lv,rv);
	}
	vector<int> inv(vector<int> v){
		vector<int> re = v;
		for(int i = 0;i<v.size();i++)re[v[i]] = i;
		return re;
	}
	vector<int> GO(int NN){
		N = NN;
		int B = __lg(N);
		vector<vector<int>> v;
		v.push_back({});
		for(int i = 0;i<N;i++)v.back().push_back(i);
		for(int i = B-1;i>=0;i--){
			vector<vector<int>> nx;
			for(auto &j:v){
				auto tmp = calc(j);
				nx.push_back(tmp.first);
				nx.push_back(tmp.second);
			}
			v = nx;
		}
		assert(v.size() == N);
		for(int i = 0;i<N;i++)ans.push_back(v[i][0]);
		cerr<<"CALC:";for(auto &i:ans)cerr<<i<<',';cerr<<endl;
		return inv(ans);
	}
}

std::vector<int> restore_permutation(int n, int w, int r) {
	WRITE::GO(n);
	compile_set();
	return READ::GO(n);
}

Compilation message (stderr)

messy.cpp: In function 'std::vector<int> READ::inv(std::vector<int>)':
messy.cpp:50:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   for(int i = 0;i<v.size();i++)re[v[i]] = i;
      |                 ~^~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from messy.cpp:4:
messy.cpp: In function 'std::vector<int> READ::GO(int)':
messy.cpp:68:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   68 |   assert(v.size() == N);
      |          ~~~~~~~~~^~~~

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