Submission #129508

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

messy

#include "messy.h"
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define sol (k+k)
#define sag (k+k+1)
#define orta ((bas+son)/2)
#define coc g[node][i]
#define inf 1000000009
#define N 1000005
using namespace std;

typedef long long ll;
typedef pair < int , int > ii;
typedef vector < int > vi;

int m, bs[N], sn[N];
string s;

void f(int bas, int son){
	if(bas >= son)
		return;
	for(int i = bas; i <= son; i++)s[i] = '0';
	for(int i = bas; i <= orta; i++){
		s[i] = '1';
		add_element(s);
		// cout << s << endl;
		s[i] = '0';
	}
	for(int i = bas; i <= son; i++)s[i] = '1';
	f(bas, orta);
	f(orta + 1, son);
}

void ff(int bas, int son){
	if(bas >= son)
		return;
	for(int i = 0; i < m; i++){
		if(bs[i] > son or sn[i] < bas)
			s[i] = '1';
		else
			s[i] = '0';
	}
	for(int i = 0; i < m; i++){
		if(s[i] == '1')
			continue;

		s[i] = '1';
		// cout << s << endl;
		if(check_element(s))
			sn[i] = orta;
		else
			bs[i] = orta + 1;
		s[i] = '0';
	}
	ff(bas, orta);
	ff(orta + 1, son);
}

vi restore_permutation(int n, int w, int r) {m = n;
	for(int i = 0; i < n; i++)
		s += '1';
	f(0, n - 1);
	for(int i = 0; i < n; i++){
		bs[i] = 0;
		sn[i] = n - 1;
	}
    compile_set();
    ff(0, n - 1);
    vi ans;
    for(int i = 0; i < n; i++)
    	ans.pb(bs[i]);
    return ans;
}

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