#include "messy.h"
#include<bits/stdc++.h>
using namespace std;
#define INIT ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
/*
add_element("0");
compile_set();
check_element("0");
*/
string s;
void build(int tl, int tr){
int mid=(tl+tr)>>1ll;
for(int i=tl ;i<=mid; i++){
s[i-1]='1';
add_element(s);
s[i-1]='0';
}
if(tl==tr){
return;
}
for(int i=tl; i<=mid; i++){
s[i-1]='1';
}
build(mid+1, tr);
for(int i=mid+1; i<=tr; i++){
s[i-1]='1';
}
for(int i=tl; i<=mid; i++){
s[i-1]='0';
}
build(tl, mid);
}
vector<int> seg[1001];
void build_seg(int v, int tl, int tr,int n){
if(tl==tr){
return;
}
int mid=(tl+tr)>>1ll;
for(int i=0; i<n; i++){
if(s[i]=='0'){
s[i]='1';
bool res=check_element(s);
if(res){
seg[v*2].pb(i);
}
s[i]='0';
}
}
for(int i:seg[v*2]){
s[i]='1';
}
for(int i=0; i<n; i++){
if(s[i]=='0'){
seg[2*v+1].pb(i);
}
}
build_seg(v*2+1, mid+1, tr, n);
for(int i:seg[2*v+1]){
s[i]='1';
}
for(int i:seg[2*v]){
s[i]='0';
}
build_seg(2*v, tl, mid, n);
}
void nulify( int n){
for(int i=0; i<n; i++){
s[i]='0';
}
}
vector<int> res;
void get_all(int v, int tl, int tr){
if(tl==tr){
res[seg[v][0] ]=tl-1;
return;
}
get_all(2*v, tl, (tl+tr)>>1ll);
get_all(2*v+1, ((tl+tr)>>1ll)+1, tr);
}
std::vector<int> restore_permutation(int n, int w, int r) {
s.resize(n);
for(int i=0; i<n; i++){
s[i]='0';
}
build(1, n);
//cout<<"b1"<<"\n"<<flush;
compile_set();
//cout<<"c\n"<<flush;
nulify(n);
//cout<<"n\n"<<flush;
build_seg(1, 1, n, n);
//cout<<"b2\n"<<flush;
res.resize(n);
get_all(1, 1, n);
//cout<<"g\n"<<flush;
return res;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
n = 8 |
2 |
Correct |
1 ms |
364 KB |
n = 8 |
3 |
Correct |
1 ms |
364 KB |
n = 8 |
4 |
Correct |
1 ms |
364 KB |
n = 8 |
5 |
Correct |
1 ms |
364 KB |
n = 8 |
6 |
Correct |
1 ms |
364 KB |
n = 8 |
7 |
Correct |
1 ms |
364 KB |
n = 8 |
8 |
Correct |
1 ms |
364 KB |
n = 8 |
9 |
Correct |
1 ms |
364 KB |
n = 8 |
10 |
Correct |
1 ms |
364 KB |
n = 8 |
11 |
Correct |
1 ms |
364 KB |
n = 8 |
12 |
Correct |
1 ms |
364 KB |
n = 8 |
13 |
Correct |
1 ms |
364 KB |
n = 8 |
14 |
Correct |
1 ms |
364 KB |
n = 8 |
15 |
Correct |
1 ms |
364 KB |
n = 8 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
n = 32 |
2 |
Correct |
1 ms |
364 KB |
n = 32 |
3 |
Correct |
1 ms |
364 KB |
n = 32 |
4 |
Correct |
1 ms |
364 KB |
n = 32 |
5 |
Correct |
1 ms |
364 KB |
n = 32 |
6 |
Correct |
1 ms |
364 KB |
n = 32 |
7 |
Correct |
1 ms |
364 KB |
n = 32 |
8 |
Correct |
1 ms |
364 KB |
n = 32 |
9 |
Correct |
1 ms |
364 KB |
n = 32 |
10 |
Correct |
1 ms |
364 KB |
n = 32 |
11 |
Correct |
1 ms |
364 KB |
n = 32 |
12 |
Correct |
1 ms |
364 KB |
n = 32 |
13 |
Correct |
1 ms |
364 KB |
n = 32 |
14 |
Correct |
1 ms |
364 KB |
n = 32 |
15 |
Correct |
1 ms |
364 KB |
n = 32 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
n = 32 |
2 |
Correct |
1 ms |
384 KB |
n = 32 |
3 |
Correct |
1 ms |
364 KB |
n = 32 |
4 |
Correct |
1 ms |
364 KB |
n = 32 |
5 |
Correct |
1 ms |
364 KB |
n = 32 |
6 |
Correct |
1 ms |
364 KB |
n = 32 |
7 |
Correct |
1 ms |
364 KB |
n = 32 |
8 |
Correct |
1 ms |
364 KB |
n = 32 |
9 |
Correct |
1 ms |
364 KB |
n = 32 |
10 |
Correct |
1 ms |
364 KB |
n = 32 |
11 |
Correct |
1 ms |
364 KB |
n = 32 |
12 |
Correct |
1 ms |
364 KB |
n = 32 |
13 |
Correct |
1 ms |
364 KB |
n = 32 |
14 |
Correct |
1 ms |
364 KB |
n = 32 |
15 |
Correct |
1 ms |
364 KB |
n = 32 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
492 KB |
n = 128 |
2 |
Correct |
2 ms |
492 KB |
n = 128 |
3 |
Correct |
2 ms |
492 KB |
n = 128 |
4 |
Correct |
2 ms |
512 KB |
n = 128 |
5 |
Correct |
2 ms |
492 KB |
n = 128 |
6 |
Correct |
2 ms |
492 KB |
n = 128 |
7 |
Correct |
2 ms |
492 KB |
n = 128 |
8 |
Correct |
2 ms |
492 KB |
n = 128 |
9 |
Correct |
2 ms |
492 KB |
n = 128 |
10 |
Correct |
2 ms |
492 KB |
n = 128 |
11 |
Correct |
2 ms |
492 KB |
n = 128 |
12 |
Correct |
2 ms |
492 KB |
n = 128 |
13 |
Correct |
2 ms |
492 KB |
n = 128 |
14 |
Correct |
2 ms |
492 KB |
n = 128 |
15 |
Correct |
2 ms |
492 KB |
n = 128 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
492 KB |
n = 128 |
2 |
Correct |
2 ms |
492 KB |
n = 128 |
3 |
Correct |
2 ms |
492 KB |
n = 128 |
4 |
Correct |
2 ms |
492 KB |
n = 128 |
5 |
Correct |
2 ms |
492 KB |
n = 128 |
6 |
Correct |
2 ms |
492 KB |
n = 128 |
7 |
Correct |
2 ms |
492 KB |
n = 128 |
8 |
Correct |
2 ms |
492 KB |
n = 128 |
9 |
Correct |
2 ms |
492 KB |
n = 128 |
10 |
Correct |
2 ms |
492 KB |
n = 128 |
11 |
Correct |
2 ms |
492 KB |
n = 128 |
12 |
Correct |
2 ms |
492 KB |
n = 128 |
13 |
Correct |
2 ms |
492 KB |
n = 128 |
14 |
Correct |
2 ms |
620 KB |
n = 128 |
15 |
Correct |
2 ms |
492 KB |
n = 128 |