Submission #1270379

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270379		WH8	Unscrambling a Messy Bug (IOI16_messy)	C++20	100 / 100	1 ms	584 KiB

messy

#include <bits/stdc++.h>
#include "messy.h"
using namespace std;

string ones;
vector<int> p;

void add(int l, int r){
	string s=ones;
	//~ cout<<"s is " << s<<endl;
	int m=(l+r)/2;
	for(int i=l;i<=r;i++){
		s[i]='0';
	}
	for(int i=l;i<=m;i++){
		s[i]='1';
		//~ cout<<"adding " << s<<endl;
		add_element(s);
		s[i]='0';
	}
	if(l!=r){
		add(l, m);
		add(m+1, r);
	}
}

void check(int l, int r, vector<int> ind){
	if(l==r){
		assert(ind.size()==1);
		p[ind[0]]=l;
		return;
	}
	string s=ones;
	vector<int> toleft, toright;
	for(auto it:ind) s[it]='0';
	for(auto it:ind){
		s[it]='1';
		if(check_element(s)){
			toleft.push_back(it);
		}
		else toright.push_back(it);
		s[it]='0';
	}
	int m=(l+r)/2;
	check(l, m, toleft);
	check(m+1, r, toright);
};

vector<int> restore_permutation(int n, int w, int r) {
	//~ cout<<"n is " << n<<endl;
	for(int i=0;i<n;i++)ones+='1';
	//~ cout<<"ones is " << ones<<endl;
	p.resize(n); fill(p.begin(),p.end(),-1);
	add(0, n-1);
    compile_set();
    vector<int> v; for(int i=0;i<n;i++)v.push_back(i);
    check(0, n-1, v);
    //~ for(auto it:p)cout<<it<<endl;
    return p;
}

Compilation message (stderr)

messy.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
messy_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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