Submission #288236

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

messy

#include<bits/stdc++.h>
#include "messy.h"
using namespace std;
#define FOR(i, x, y) for(int i = x; i < y; ++i)
#define pb push_back

int N;
vector<int> P;

vector<string> addreq(int n){
	if (n == 2){
		return {"10"};
	}
	else{
		vector<string> tmp = addreq(n/2);
		vector<string> ans(tmp.size()*2 + n/2);
		string app(n/2, '1');
		string base(n, '0');
	//	cout << "appbase\n";
	//	cout << app << "\n";
	//	cout << base << "\n";
		FOR(i, 0, n/2){
			ans[i] = base;
			ans[i][i] = '1';
		}
		FOR(i, 0, tmp.size()){
			ans[i + n/2] = tmp[i] + app;
		}
		FOR(i, 0, tmp.size()){
			ans[i + n/2 + tmp.size()] = app + tmp[i];
		}
		return ans;
	}
}

void solve (int start, int end, vector<int>& pos){
	//inclusive-exclusive
	string base(N, '1');
	FOR(i, 0, pos.size()){
		base[pos[i]] = '0';
//		cout << pos[i] << "\n";
	}
//	cout << "base: " << base << "\n";
	if (end - start == 2){
//		cout << "base case\n";
		base[pos[0]] = '1';
//		cout << base << "\n";
		if (check_element(base)){
//			cout << "True\n";
			P[pos[0]] = start;
			P[pos[1]] = start + 1;
		}
		else{
//			cout << "False\n";
			P[pos[0]] = start + 1;
			P[pos[1]] = start;
		}
		return;
	}
	vector<int> fi;
	vector<int> se;
	FOR(i, 0, pos.size() - 1){
		base[pos[i]] = '1';
		bool store = check_element(base);
		if (store){
			fi.pb(pos[i]);
		}
		else{
			se.pb(pos[i]);
		}
		base[pos[i]] = '0';
	}
	if (fi.size() == (end - start)/2){
		se.pb(pos.back());
	}
	else{
		fi.pb(pos.back());
	}
	solve(start, start + (end - start)/2, fi);
	solve(start + (end - start)/2, end, se);
}


vector<int> restore_permutation(int n, int w, int r) {
	N = n;
	P.resize(n);
	vector<string> W = addreq(n);
	FOR(i, 0, W.size()){
		//cout << W[i] << "\n";
		add_element(W[i]);
	}
	compile_set();
	//check_element("0");
	vector<int> work(n);
	FOR(i, 0, n){
		work[i] = i;
	}
//	cout << "here\n";
	solve(0, n, work);
//	cout << "here\n";
//	FOR(i, 0, P.size()){
//		cout << P[i] << " ";
//	}
//	cout << "\n";
	return P;
}

Compilation message (stderr)

messy.cpp: In function 'std::vector<std::__cxx11::basic_string<char> > addreq(int)':
messy.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
   26 |   FOR(i, 0, tmp.size()){
      |       ~~~~~~~~~~~~~~~~                 
messy.cpp:26:3: note: in expansion of macro 'FOR'
   26 |   FOR(i, 0, tmp.size()){
      |   ^~~
messy.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
   29 |   FOR(i, 0, tmp.size()){
      |       ~~~~~~~~~~~~~~~~                 
messy.cpp:29:3: note: in expansion of macro 'FOR'
   29 |   FOR(i, 0, tmp.size()){
      |   ^~~
messy.cpp: In function 'void solve(int, int, std::vector<int>&)':
messy.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
   39 |  FOR(i, 0, pos.size()){
      |      ~~~~~~~~~~~~~~~~                  
messy.cpp:39:2: note: in expansion of macro 'FOR'
   39 |  FOR(i, 0, pos.size()){
      |  ^~~
messy.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
   62 |  FOR(i, 0, pos.size() - 1){
      |      ~~~~~~~~~~~~~~~~~~~~              
messy.cpp:62:2: note: in expansion of macro 'FOR'
   62 |  FOR(i, 0, pos.size() - 1){
      |  ^~~
messy.cpp:73:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   73 |  if (fi.size() == (end - start)/2){
      |      ~~~~~~~~~~^~~~~~~~~~~~~~~~~~
messy.cpp: In function 'std::vector<int> restore_permutation(int, int, int)':
messy.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
   88 |  FOR(i, 0, W.size()){
      |      ~~~~~~~~~~~~~~                    
messy.cpp:88:2: note: in expansion of macro 'FOR'
   88 |  FOR(i, 0, W.size()){
      |  ^~~

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