Submission #1182964

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

messy

#include "messy.h"
#include <bits/stdc++.h>
#define sz(x) (int)(x).size()
using namespace std;

// 2 1 3 0 -> 3 1 0 2
vector<int> p;

void dq(int l, int r, set<int> &pos) {
	if (l==r) {
		p[l]=*pos.begin();
		return;
	}
	string s(sz(p), '1'); for (auto &u: pos) s[u]='0';
	set<int> sl, sr;
	for (auto &u: pos) {
		s[u]='1';
		if (check_element(s)) {
			sl.insert(u);
		} else sr.insert(u);
		s[u]='0';
	}
	int m=(l+r)/2;
	dq(l, m, sl), dq(m+1, r, sr);
}

vector<int> restore_permutation(int n, int w, int r) {
	for (int val=1; val<n; val*=2) {
		for (int i=0; i<n; i+=val*2) {
			string s(n, '1');
			for (int j=i; j<i+2*val; j++) s[j]='0';
			for (int j=i; j<i+val; j++) {
				s[j]='1';
				add_element(s);
				s[j]='0';
			}
		}
	}
	compile_set();
	set<int> pos; for (int i=0; i<n; i++) pos.insert(i);
	p.resize(n);
	dq(0, n-1, pos);
	vector<int> np(n); for (int i=0; i<n; i++) np[p[i]]=i;
	return np;
}

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