Submission #1253372

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253372		Nurislam	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;


vector<int> ans;

void ad(int l, int r, string s) {
	if(l == r) return;
	
	int m = (l+r) >> 1;
	
	for(int i = l; i <= m; i ++ ) {
		s[i] = '1';
		add_element(s);
		s[i] = '0';
	};
	string sl = s, sr = s;
	for(int i = l; i <= r; i ++ ) {
		if(i <= m)sr[i] = '1';
		else sl[i] = '1';
	};
	
	ad(l, m, sl);
	ad(m+1, r, sr);
	
};


void rt (int l, int r, string s, vector<int> &v) {
	if(l == r) {
		ans[v[0]] = l;
		return;
	};
	
	int m = (l + r) >> 1;
	
	vector<int> vl, vr;
	for(int i : v) {
		s[i] = '1';
		if(check_element(s)) vl.push_back(i);
		else vr.push_back(i);
		s[i] = '0';
	};
	string sl = s, sr = s;
	for(int i : vr) sl[i] = '1';
	for(int i : vl) sr[i] = '1';
	
	
	rt(l, m, sl, vl);
	rt(m+1, r, sr, vr);
	
};


vector<int> restore_permutation(int n, int w, int r) {
    //add_element("0");
    //compile_set();
    //check_element("0");
    //return vector<int>();
    string s;
    s.resize(n, '0');
    ad(0, n-1, s);
    compile_set();
    
    ans.resize(n);
    for(auto &i : s) i = '0';
    vector<int> v(n);
    iota(v.begin(), v.end(), 0);
    rt(0, n-1, s, v);
    
    return ans;
}

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