Submission #139788

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

messy

#include "messy.h"
#include <bits/stdc++.h>

#define pb push_back
#define mp make_pair
#define inside sl<=l&&r<=sr
#define outside r<sl||sr<l
#define orta ((l+r)>>1)
#define INF 1000000009
#define mod 1000000007
#define ppair(x); cerr << "(" << x.first << ", " << x.second << ")\n";
#define bas(x) #x << ": " << x << " "
#define prarr(x, n); cerr << #x << ": "; for(int qsd = 0; qsd < n; qsd++) cerr << x[qsd] << " "; cerr << "\n";
#define prarrv(x); cerr << #x << ": "; for(int qsd = 0; qsd < (int)x.size(); qsd++) cerr << x[qsd] << " "; cerr << "\n";
using namespace std;
typedef long long ll;

int n, w, r;
vector<int> ans;

void ekle(int l, int r){
	//cout << "ekle(" << l << ", " << r << ")" << endl;
	if (l == r) return;
	string add = "";
	for (int i = 0; i < n; i++) add += '1';
	for (int i = l; i <= r; i++) add[i] = '0';
	int m = (l+r)/2;
	for (int i = l; i <= m; i++){
		add[i] = '1';
		//cout << add << endl;
		add_element(add);
		add[i] = '0';
	}
	
	ekle(l, m);
	ekle(m+1, r);
}

void solve(int l, int r, vector<int>& arr, vector<int>& diger){
	string get = "";
	for (int i = 0; i < n; i++) get += '0';
	for (int i = 0; i < diger.size(); i++) get[diger[i]] = '1';
	vector<int> sol;
	vector<int> sag;
	for (int i = 0; i < n; i++){
		if (get[i] == '1') continue;
		get[i] = '1';
		if (check_element(get)) sol.pb(i);
		else sag.pb(i);
		get[i] = '0';
	}
	if (sol.size() == 1){
		ans[sol[0]] = l;
		ans[sag[0]] = r;
		return;
	}
	vector<int> digersol = diger;
	vector<int> digersag = diger;
	for (int i = 0; i < sol.size(); i++) digersag.pb(sol[i]);
	for (int i = 0; i < sag.size(); i++) digersol.pb(sag[i]);
	int m = (l+r)/2;
	solve(l, m, sol, digersol);
	solve(m+1, r, sag, digersag);
}

vector<int> restore_permutation(int N, int W, int R) {
	n = N;
	w = W;
	r = R;
	
	string add = "";
	for (int i = 0; i < n; i++) add += "0";
	for (int i = 0; i < n/2; i++){
		add[i] = '1';
		//cout << add << endl;
		add_element(add);
		add[i] = '0';
	}
	ekle(0, n/2-1);
	ekle(n/2, n-1);
	
	compile_set();
	
	ans.resize(n);
	
	vector<int> sol;
	vector<int> sag;
	
	for (int i = 0; i < n; i++){
		add[i] = '1';
		if (check_element(add)) sol.pb(i);
		else sag.pb(i);
		add[i] = '0';
	}
	
	solve(0, n/2-1, sol, sag);
	solve(n/2, n-1, sag, sol);
	
    /*add_element("0000");
    compile_set();
    check_element("0000");*/
    return ans;
}

Compilation message (stderr)

messy.cpp: In function 'void solve(int, int, std::vector<int>&, std::vector<int>&)':
messy.cpp:42:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < diger.size(); i++) get[diger[i]] = '1';
                  ~~^~~~~~~~~~~~~~
messy.cpp:59:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < sol.size(); i++) digersag.pb(sol[i]);
                  ~~^~~~~~~~~~~~
messy.cpp:60:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < sag.size(); i++) digersol.pb(sag[i]);
                  ~~^~~~~~~~~~~~

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