| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 198354 | nvmdava | Unscrambling a Messy Bug (IOI16_messy) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include<messy.h>
using namespace std;
int N;
/*
int perm[202];
set<string> test, tru;
// to be removed when submitting
void add_element(string s)
{
test.insert(s);
}
bool check_element(string s)
{
if(tru.find(s) != tru.end())
return 1;
return 0;
}
void compile_set()
{
string ans;
for(int i = 0; i < N; ++i)
ans += '0';
for(set<string> ::iterator it = test.begin(); it != test.end(); ++it)
{
string ss = *it;
for(int i = 0; i < N; ++i)
ans[i] = '0';
for(int i = 0; i < N; ++i)
ans[perm[i]] = ss[i];
tru.insert(ans);
}
}
*/
int poz[202];
vector<int> pospoz[202][202];
void build(int st, int dr)
{
if(st == dr)
return;
string s;
for(int i = 0; i < N; ++i)
s += '1';
int mid = (st + dr) / 2;
for(int i = st; i <= dr; ++i)
s[i] = '0';
for(int i = st; i <= mid; ++i)
{
s[i] = '1';
assert((int) s.size() == N);
add_element(s);
s[i] = '0';
}
build(st, mid);
build(mid+1, dr);
}
void restore(int st, int dr)
{
if(st == dr)
{
poz[st] = pospoz[st][st][0];
return;
}
string s;
for(int i = 0; i < N; ++i)
s += '0';
bool oki[150];
for(int i = 0; i < 150; ++i)
ok[i] = 0;
for(int i = 0; i < pospoz[st][dr].size(); ++i)
oki[pospoz[st][dr][i]] = 1;
for(int i = 0; i < N; ++i)
if(!oki[i])
s[i] = '1';
int mid = (st + dr) / 2;
for(int i = 0; i < pospoz[st][dr].size(); ++i)
{
int pp = pospoz[st][dr][i];
s[pp] = '1';
assert((int) s.size() == N);
bool xxx = check_element(s);
if(xxx)
pospoz[st][mid].push_back(pp);
else
pospoz[mid+1][dr].push_back(pp);
s[pp] = '0';
}
restore(st, mid);
restore(mid+1, dr);
}
vector<int> restore_permutation(int n, int w, int r)
{
N = n;
build(0, n-1);
compile_set();
for(int i = 0; i < n; ++i)
pospoz[0][n-1].push_back(i);
restore(0, n-1);
vector<int> ans;
for(int i = 0; i < n; ++i)
ans.push_back(poz[i]);
assert((int) ans.size() == N);
return ans;
}