| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1065637 | Hectorungo_18 | Aliens (IOI16_aliens) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "messy.h"
using namespace std;
mt19937 gnd(time(nullptr));
// #define int long long
void ch(string& s, int pos, char c){
s[pos]=c;
return;
}
vector<int> restore_permutation(int n, int w, int r){
int mxb = 6;
int bb = 0;
int aux = n;
while(aux > 1){
bb++;
aux/=2;
}
mxb = bb-1;
cout << mxb << endl;
string s (n, '0');
char u = '1', c = '0';
for(int bi = mxb; bi >= 0 ; bi--){
if(bi == mxb){
for(int i = n/2; i < n; i++){
ch(s, i, u);
add_element(s);
ch(s, i, c);
}
}
else{
for(int i = 0; i < (1<<(bi+1)); i++){
ch(s, i, u);
}
for(int i = n/2+(1<<bi); i < n; i+=(1<<(bi+1))){
for(int j = i; j < i+(1<<(bi)); j++){
ch(s, j, u);
add_element(s);
ch(s, j, c);
}
}
for(int i = 0; i < (1<<(bi+1)); i++){
ch(s, i, c);
}
for(int i = n/2; i < n/2+(1<<(bi+1)); i++){
ch(s, i, u);
}
for(int i = (1<<bi); i < n/2; i+=(1<<(bi+1))){
for(int j = i; j < i+(1<<(bi)); j++){
ch(s, j, u);
add_element(s);
ch(s, j, c);
}
}
for(int i = n/2; i < n/2+(1<<(bi+1)); i++){
ch(s, i, c);
}
}
}
compile_set();
vector<int> ans(n, 0);
set<int> fh, sh;
vector<int> ffh, ssh;
for(int bi = mxb; bi >= 0; bi--){
if(bi == mxb){
for(int i = 0; i < n; i++){
ch(s, i, u);
int a = check_element(s);
ch(s, i, c);
if(a){
ans[i]+=(1<<bi);
sh.insert(i);
ssh.push_back(i);
}
else{
fh.insert(i);
ffh.push_back(i);
}
}
}
else{
set<int> aux = sh;
for(auto x : fh){
ch(s, x, u);
}
for(auto x : ssh){
ch(s, x, u);
int a = check_element(s);
ch(s, x, c);
if(a){
if(sh.count(x)) sh.erase(x);
ans[x]+=(1<<bi);
}
// else{
// }
}
for(auto x : fh){
ch(s, x, c);
}
for(auto x : aux){
ch(s, x, u);
}
for(auto x : ffh){
ch(s, x, u);
int a = check_element(s);
ch(s, x, c);
if(a){
if(fh.count(x)) fh.erase(x);
ans[x]+=(1<<bi);
}
}
for(auto x : aux){
ch(s, x, c);
}
}
}
return ans;
}