| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1095372 | idiotcomputer | Unscrambling a Messy Bug (IOI16_messy) | C++11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#include "messy.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int) (x).size()
#define pii pair<int,int>
#define f first
#define s second
#define pb push_back
#include <random>
void cl(string &t){
for (int i = 0; i < sz(t); i++) t[i] = '0';
}
bool chin(vector<int> &a, int v){
for (int c : a) if (c == v) return 1;
return 0;
}
vector<int> restore_permutation(int n, int w, int r){
int k = 0;
int c = 1;
while (c < n){
c *= 2;
k++;
}
k = max(4,k);
string t = "";
for (int i = 0; i < n; i++) t += '0';
for (int i = 0; i < k; i++){
cl(t);
t[i] = '1';
add_element(t);
for (int j = 0; j < i; j++) t[j] = '1';
add_element(t);
}
cl(t);
add_element(t);
t[0] = '1';
t[k-1] = '1';
add_element(t);
vector<pii> ranges;
vector<pii> nex;
ranges.pb((pii){k,n-1});
int mid;
for (int i = 0; i < k; i++){
nex.clear();
//cout << i << ": \n";
for (pii c : ranges){
if (c.f == c.s) continue;
mid = (c.s + c.f)/2;
nex.pb((pii) {c.f,mid});
nex.pb((pii) {mid+1,c.s});
//cout << c.f << " " << c.s << "\n";
for (int j = mid+1; j <= c.s; j++){
cl(t);
t[j] = '1';
for (int i2 = 0; i2 <= i; i2++) t[i2] = '1';
add_element(t);
}
}
swap(ranges,nex);
}
/*cout << k << "\n";
for (string &c : all) cout << c << "\n";
cout << "COMPILING:\n";*/
compile_set();
vector<int> ipos;
//cout << c2 << '\n';
for (int i = 0; i < n; i++){
cl(t);
t[i] = '1';
if (check_element(t)) ipos.pb(i);
}
//for (int c : ipos) cout << c << ' ';
//cout << "\n";
//cout << k << " " << c2 << '\n';
vector<int> ord;
for (int i = 0; i < k-2; i++){
for (int c : ipos){
if (chin(ord,c)) continue;
cl(t);
for (int ct : ipos) t[ct] = '1';
for (int ct : ord) t[ct] = '0';
t[c] = '0';
//if (i == 2) cout << c << " " << t << '\n';
if (!check_element(t)) continue;
ord.pb(c);
if (i == 0 && c == 0) cout <<"IN "<< t << '\n';
break;
}
}
//cout << c2 << '\n';
for (int c : ipos){
if (chin(ord,c)) continue;
cl(t);
t[c] = '1';
t[ord[0]] = '1';
if (!check_element(t)){ ord.pb(c); break;}
}
//cout << c2 << '\n';
for (int c : ipos) if (!chin(ord,c)){ ord.pb(c); break; }
/*for (int c : ord) cout << c << ' ';
cout << "\n";*/
for (int i = 0; i < k/2; i++) swap(ord[i],ord[k-i-1]);
/*for (int c : ord) cout << c << ' ';
cout << "\n";*/
//cout << k << " " << c2 << '\n';
vector<int> res(n);
bool vis[n];
memset(vis,0,sizeof(vis));
//pii range[n];
//for (int i = 0; i < n; i++) range[i] = {k,n-1};
//for (int i = 0; i < k; i++) range[ord[i]] = {i,i};
//cout << k << " " << n << '\n';
for (int i = 0; i < n; i++){
if (chin(ord,i)) continue;
pii cur = {k,n-1};
int ck = 0;
while (1){
int cnt = -1;
for (int j = cur.f; j <= cur.s; j++){
if (vis[j]) continue;
if (cnt != -1){ cnt = -2; break;}
cnt = j;
}
if (cnt > -1){
res[i] = cnt;
vis[cnt] = 1;
break;
}
cl(t);
for (int j = 0; j <= ck; j++) t[ord[j]] = '1';
t[i] = '1';
if (check_element(t)) cur = {(cur.f+cur.s)/2+1, cur.s};
else cur = {cur.f, (cur.f+cur.s)/2};
ck++;
}
}
for (int i = 0; i < k; i++) res[ord[i]] = i;
//for (int i = 0; i < n; i++) res[i] = range[i].f;
return res;
}