# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
67585 | mirbek01 | Unscrambling a Messy Bug (IOI16_messy) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "messy.h"
//#include "grader.cpp"
using namespace std;
string s;
vector <int> ans, vv;
void fun(int l, int r){
if(l >= r) return ;
s = "";
for(int i = 0; i < n; i ++){
if(l <= i && i <= r)
s += '0';
else
s += '1';
}
int md = (l + r) >> 1;
for(int i = l; i <= md; i ++){
s[i] = '1';
add_element(s);
s[i] = '0';
}
fun(l, md);
fun(md + 1, r);
}
void rec(int l, int r){
if(l >= r){
return ;
}
s.resize(n);
for(int i = 0; i < n; i ++){
if(l <= i && i <= r)
s[ans[i]] = '0';
else
s[ans[i]] = '1';
}
vector < int > v1, v2;
int md = (l + r) >> 1;
for(int i = l; i <= r; i ++){
s[ans[i]] = '1';
if(check_element(s))
v1.push_back(ans[i]);
else
v2.push_back(ans[i]);
s[ans[i]] = '0';
}
int p1 = 0, p2 = 0;
for(int i = l; i <= r; i ++){
if(i <= md){
ans[i] = v1[p1 ++];
} else {
ans[i] = v2[p2 ++];
}
}
rec(l, md);
rec(md + 1, r);
}
vector<int> restore_permutation(int NN, int w, int r) {
ans.resize(n);
vv.resize(n);
for(int i = 0; i < n; i ++)
ans[i] = i;
fun(0, n - 1);
compile_set();
rec(0, n - 1);
for(int i = 0; i < n; i ++){
vv[ans[i]] = i;
}
return vv;
}