Submission #119223

#	Time	Username	Problem	Language	Result	Execution time	Memory
119223		patrikpavic2	Unscrambling a Messy Bug (IOI16_messy)	C++17	100 / 100	4 ms	640 KiB

messy

#include "messy.h"
#include <vector>
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef vector < int > vi;

const int N = 150;

int n, sol[N];

void dodaj(int l,int r){
	if(l == r) return;
	string s;
	for(int i = 0;i < n;i++){
		if(l <= i && i <= r)
			s.PB('0');
		else
			s.PB('1');
	}
	for(int i = (l + r) / 2 + 1;i <= r;i++){
		s[i] = '1';
		add_element(s);
		s[i] = '0';
	}
	dodaj(l, (l + r) / 2);
	dodaj((l + r) / 2 + 1, r);
	
}	

void rijesi(vi p,int l,int r){
//	cout << l << " " << r << "\n";
//	cout << "P : ";
//	for(int x : p) cout << x << " ";
//	cout << "\n";
	if(l == r){
		sol[p[0]] = l;
		//cout << "gotov\n";
		return;
	}
	string s;
	for(int i = 0;i < n;i++)
		s.PB('1');
	vi L, R;
	for(int x : p)
		s[x] = '0';
//	cout << "tu sam";
	for(int x : p){
		s[x] = '1';
		if(check_element(s))
			R.PB(x);
		else
			L.PB(x);
		s[x] = '0';
	}
//	cout << "tu sam";
	rijesi(L, l, (l + r) / 2);
	rijesi(R, (l + r) / 2 + 1, r);
}

vi restore_permutation(int nn, int w, int r) {
    n = nn;
    vi ret;
    dodaj(0, n - 1);
    //cout << "gotovo dodavanje/n";
   // return vi();
    for(int i = 0;i < n;i++) ret.PB(i);
    compile_set();
    rijesi(ret, 0, n - 1);
    ret.clear();
    for(int i = 0;i < n;i++) ret.PB(sol[i]);
    return ret;
}

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