Submission #227857

#	Time	Username	Problem	Language	Result	Execution time	Memory
227857		cfalas	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	7 ms	512 KiB

messy

#include<bits/stdc++.h>
#include "messy.h"
#define MID ((l+r)/2)
using namespace std;
typedef vector<int> vi;

int t;
int cnt=0;
string s;
void build(int l=0, int r=t-1){
	if(l==r)
		return;
	for(int i=0; i<l;i++) s[i]='1';
	for(int i=l; i<=r;i++) s[i]='0';
	for(int i=r+1; i<t;i++) s[i]='1';
	for(int i=l; i<=MID; i++) {
		s[i]='1';
		//cout<<s<<endl;
		add_element(s);
		s[i]='0';
	}
	build(l, MID);
	build(MID+1, r);
}

bool used[10000];
vector<int> p;

void f(vi a, int l=0, int r=t-1){
	//cout<<l<<" "<<r<<endl;
	if(l==r){ p[a[0]]=t-l-1; return;}

	string test(t, '1');
	for(int i=0;i<a.size();i++) test[a[i]] = '0';
	vi c, d;
	for(auto &j : a){
		test[j] = '1';

		//cout<<"testing: "<<test<<" ";
		if(check_element(test)){
			//cout<<"f";
			d.push_back(j);
		}
		else c.push_back(j);
		//cout<<endl;

		test[j] = '0';
	}
	f(c, l, MID);
	f(d, MID+1, r);
}

vector<int> restore_permutation(int n, int w, int r) {
	t = n;
	int l = round(log2(n));
	p.assign(n,0);
	s.assign(n,'0');
	build();
	compile_set();

	for(int i=0;i<n;i++) p[i] = i;
	f(p);
    return p;
}

Compilation message (stderr)

messy.cpp: In function 'void f(vi, int, int)':
messy.cpp:34:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a.size();i++) test[a[i]] = '0';
              ~^~~~~~~~~
messy.cpp: In function 'std::vector<int> restore_permutation(int, int, int)':
messy.cpp:55:6: warning: unused variable 'l' [-Wunused-variable]
  int l = round(log2(n));
      ^

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