Submission #290172

#	Time	Username	Problem	Language	Result	Execution time	Memory
290172		shayan_p	Unscrambling a Messy Bug (IOI16_messy)	C++17	100 / 100	3 ms	512 KiB

messy

#include<bits/stdc++.h>
#include "messy.h"

#define F first
#define S second
#define PB push_back
#define sz(s) (int(s.size()))
#define bit(n, k) (((n)>>(k)) & 1)

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

const int maxn = 210, mod = 1e9 + 7, inf = 1e9 + 10;

string s;

void go_add(int l, int r){
    if(r-l <= 2)
	return;
    int mid = (l+r) >> 1;
    for(int i = l; i < mid; i++)
	s[i] = '1';
    int MID = (mid + r) >> 1;
    for(int i = MID; i < r; i++){
	s[i] = '1';
	add_element(s);
	s[i] = '0';
    }
    for(int i = l; i < mid; i++)
	s[i] = '0';

    for(int i = mid; i < r; i++)
	s[i] = '1';
    MID = (l + mid) >> 1;
    for(int i = MID; i < mid; i++){
	s[i] = '1';
	add_element(s);
	s[i] = '0';
    }
    for(int i = mid; i < r; i++)
	s[i] = '0';
    go_add(l, mid);
    go_add(mid, r);
}

vector<int> ans;

void go_check(vector<int> ZR, vector<int> ON, int l, int r){
    if(r-l <= 2){
	assert(r-l == 2);
	assert(sz(ZR) == 1);
	assert(sz(ON) == 1);
	ans[ZR[0]] = l;
	ans[ON[0]] = l+1;
	return;
    }
    int mid = (l+r) >> 1;
    
    vector<int> _ZR, _ON;    
    for(int x : ZR)
	s[x] = '1';
    for(int x : ON){
	s[x] = '1';
	if(check_element(s))
	    _ON.PB(x);
	else
	    _ZR.PB(x);
	s[x] = '0';
    }
    for(int x : ZR)
	s[x] = '0';
    go_check(_ZR, _ON, mid, r);

    _ZR.clear(), _ON.clear();
    for(int x : ON)
	s[x] = '1';
    for(int x : ZR){
	s[x] = '1';
	if(check_element(s))
	    _ON.PB(x);
	else
	    _ZR.PB(x);
	s[x] = '0';
    }
    for(int x : ON)
	s[x] = '0';
    go_check(_ZR, _ON, l, mid);
}
vector<int> restore_permutation(int n, int w, int r){
    for(int i = 0; i < n; i++)
	s.PB('0');
    for(int i = (n/2); i < n; i++){
	s[i] = '1';
	add_element(s);
	s[i] = '0';
    }
    go_add(0, n);
    compile_set();
    vector<int> ZR, ON;
    for(int i = 0; i < n; i++){
	s[i] = '1';
	if(check_element(s))
	    ON.PB(i);
	else
	    ZR.PB(i);
	s[i] = '0';
    }
    ans.resize(n);
    go_check(ZR, ON, 0, n);
    return ans;
}

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