#include<bits/stdc++.h> //:3
using namespace std;
typedef long long ll;
#define all(a) (a).begin(), (a).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define rc(s) return cout<<s,0
#define pi pair <int, int>
#define sz(x) (int)((x).size())
#include "messy.h"
void dfs(int l, int r, int n){
if(l == r)return;
string s = "";
for(int i = 1; i <= n; i++){
s += (i < l || i > r ? '1' : '0');
}
int mid = (l + r) >> 1;
for(int i = l; i <= mid; i++){
s[i - 1] = '1';
add_element(s);
s[i - 1] = '0';
}
dfs(l, mid, n);
dfs(mid + 1, r, n);
}
vector<int> ans;
void dfs(int n, int l, int r, string s){
if(l == r)return;
n = sz(s);
vector<int>L, R;
for(int i = 1; i <= n; i++){
if(s[i - 1] == '1')continue;
s[i - 1] = '1';
if(check_element(s))L.push_back(i); else R.push_back(i);
s[i - 1] = '0';
}
if(sz(L) == 1){
ans[L[0] - 1] = l - 1;
ans[R[0] - 1] = r - 1;
}
int mid = (l + r) >> 1;
for(auto it : L){
s[it - 1] = '1';
}
dfs(n, mid + 1, r, s);
for(auto it : L){
s[it - 1] = '0';
}
for(auto it : R){
s[it - 1] = '1';
}
dfs(n, l, mid, s);
}
vector<int> restore_permutation(int n, int w, int r){
dfs(1, n, n);
compile_set();
string s;
for(int i = 1; i <= n; i++)s.push_back('0');
ans.resize(n);
dfs(n, 1, n, s);
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
256 KB |
n = 8 |
2 |
Correct |
1 ms |
256 KB |
n = 8 |
3 |
Correct |
1 ms |
296 KB |
n = 8 |
4 |
Correct |
1 ms |
256 KB |
n = 8 |
5 |
Correct |
1 ms |
256 KB |
n = 8 |
6 |
Correct |
1 ms |
384 KB |
n = 8 |
7 |
Correct |
0 ms |
256 KB |
n = 8 |
8 |
Correct |
0 ms |
256 KB |
n = 8 |
9 |
Correct |
1 ms |
384 KB |
n = 8 |
10 |
Correct |
0 ms |
256 KB |
n = 8 |
11 |
Correct |
1 ms |
256 KB |
n = 8 |
12 |
Correct |
1 ms |
256 KB |
n = 8 |
13 |
Correct |
0 ms |
384 KB |
n = 8 |
14 |
Correct |
0 ms |
256 KB |
n = 8 |
15 |
Correct |
0 ms |
256 KB |
n = 8 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
n = 32 |
2 |
Correct |
1 ms |
384 KB |
n = 32 |
3 |
Correct |
1 ms |
384 KB |
n = 32 |
4 |
Correct |
1 ms |
384 KB |
n = 32 |
5 |
Correct |
1 ms |
384 KB |
n = 32 |
6 |
Correct |
1 ms |
384 KB |
n = 32 |
7 |
Correct |
1 ms |
384 KB |
n = 32 |
8 |
Correct |
1 ms |
384 KB |
n = 32 |
9 |
Correct |
1 ms |
384 KB |
n = 32 |
10 |
Correct |
1 ms |
384 KB |
n = 32 |
11 |
Correct |
1 ms |
384 KB |
n = 32 |
12 |
Correct |
5 ms |
384 KB |
n = 32 |
13 |
Correct |
1 ms |
384 KB |
n = 32 |
14 |
Correct |
1 ms |
384 KB |
n = 32 |
15 |
Correct |
1 ms |
384 KB |
n = 32 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
512 KB |
n = 32 |
2 |
Correct |
1 ms |
384 KB |
n = 32 |
3 |
Correct |
1 ms |
384 KB |
n = 32 |
4 |
Correct |
1 ms |
384 KB |
n = 32 |
5 |
Correct |
1 ms |
372 KB |
n = 32 |
6 |
Correct |
1 ms |
384 KB |
n = 32 |
7 |
Correct |
1 ms |
384 KB |
n = 32 |
8 |
Correct |
1 ms |
384 KB |
n = 32 |
9 |
Correct |
1 ms |
384 KB |
n = 32 |
10 |
Correct |
1 ms |
384 KB |
n = 32 |
11 |
Correct |
1 ms |
384 KB |
n = 32 |
12 |
Correct |
1 ms |
384 KB |
n = 32 |
13 |
Correct |
1 ms |
384 KB |
n = 32 |
14 |
Correct |
1 ms |
384 KB |
n = 32 |
15 |
Correct |
1 ms |
384 KB |
n = 32 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
512 KB |
n = 128 |
2 |
Correct |
2 ms |
512 KB |
n = 128 |
3 |
Correct |
2 ms |
512 KB |
n = 128 |
4 |
Correct |
2 ms |
512 KB |
n = 128 |
5 |
Correct |
2 ms |
512 KB |
n = 128 |
6 |
Correct |
2 ms |
512 KB |
n = 128 |
7 |
Correct |
2 ms |
512 KB |
n = 128 |
8 |
Correct |
2 ms |
512 KB |
n = 128 |
9 |
Correct |
2 ms |
512 KB |
n = 128 |
10 |
Correct |
3 ms |
512 KB |
n = 128 |
11 |
Correct |
2 ms |
512 KB |
n = 128 |
12 |
Correct |
2 ms |
512 KB |
n = 128 |
13 |
Correct |
2 ms |
512 KB |
n = 128 |
14 |
Correct |
3 ms |
512 KB |
n = 128 |
15 |
Correct |
2 ms |
512 KB |
n = 128 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
512 KB |
n = 128 |
2 |
Correct |
2 ms |
512 KB |
n = 128 |
3 |
Correct |
2 ms |
512 KB |
n = 128 |
4 |
Correct |
2 ms |
512 KB |
n = 128 |
5 |
Correct |
2 ms |
512 KB |
n = 128 |
6 |
Correct |
2 ms |
512 KB |
n = 128 |
7 |
Correct |
2 ms |
512 KB |
n = 128 |
8 |
Correct |
2 ms |
512 KB |
n = 128 |
9 |
Correct |
2 ms |
512 KB |
n = 128 |
10 |
Correct |
2 ms |
512 KB |
n = 128 |
11 |
Correct |
2 ms |
512 KB |
n = 128 |
12 |
Correct |
2 ms |
512 KB |
n = 128 |
13 |
Correct |
2 ms |
512 KB |
n = 128 |
14 |
Correct |
2 ms |
512 KB |
n = 128 |
15 |
Correct |
2 ms |
512 KB |
n = 128 |