#include <vector>
#include "messy.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;
void debug_out() {cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
cerr << H << ' ';
debug_out(T...);
}
#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
int n;
string s;
void build(int l, int r){
if (l + 1 == r) return;
int mid = (l + r) >> 1;
for (int i = l; i < mid; i++){
s[i] = '1';
//debug(s);
add_element(s);
s[i] = '0';
}
for (int i = mid; i < r; i++){
s[i] = '1';
}
build(l, mid);
for (int i = mid; i < r; i++){
s[i] = '0';
}
for (int i = l; i < mid; i++){
s[i] = '1';
}
build(mid, r);
for (int i = l; i < mid; i++){
s[i] = '0';
}
}
const int maxn = 1e5 + 10;
int p[maxn];
void solve(vector<int> idx, int l, int r){
if (l + 1 == r){
p[idx[0]] = l;
return;
}
vector<int> lc, rc;
for (auto x: idx){
s[x] = '1';
if (check_element(s)) lc.push_back(x);
else rc.push_back(x);
s[x] = '0';
}
int mid = (l + r) >> 1;
for (auto x: rc) s[x] = '1';
solve(lc, l, mid);
for (auto x: rc) s[x] = '0';
for (auto x: lc) s[x] = '1';
solve(rc, mid, r);
for (auto x: lc) s[x] = '0';
}
vector<int> restore_permutation(int N, int w, int r) {
n = N;
for (int i = 0; i < n; i++) s.push_back('0');
build(0, n);
compile_set();
vector<int> idx;
for (int i = 0; i < n; i++){
idx.push_back(i);
}
solve(idx, 0, n);
vector<int> ans(n);
for (int i = 0; i < n; i++) ans[i] = p[i];
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
n = 8 |
2 |
Correct |
0 ms |
212 KB |
n = 8 |
3 |
Correct |
0 ms |
212 KB |
n = 8 |
4 |
Correct |
1 ms |
212 KB |
n = 8 |
5 |
Correct |
1 ms |
212 KB |
n = 8 |
6 |
Correct |
0 ms |
212 KB |
n = 8 |
7 |
Correct |
0 ms |
212 KB |
n = 8 |
8 |
Correct |
0 ms |
212 KB |
n = 8 |
9 |
Correct |
0 ms |
212 KB |
n = 8 |
10 |
Correct |
1 ms |
212 KB |
n = 8 |
11 |
Correct |
0 ms |
212 KB |
n = 8 |
12 |
Correct |
0 ms |
212 KB |
n = 8 |
13 |
Correct |
0 ms |
212 KB |
n = 8 |
14 |
Correct |
0 ms |
212 KB |
n = 8 |
15 |
Correct |
0 ms |
212 KB |
n = 8 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
n = 32 |
2 |
Correct |
1 ms |
312 KB |
n = 32 |
3 |
Correct |
1 ms |
212 KB |
n = 32 |
4 |
Correct |
1 ms |
212 KB |
n = 32 |
5 |
Correct |
1 ms |
212 KB |
n = 32 |
6 |
Correct |
1 ms |
212 KB |
n = 32 |
7 |
Correct |
1 ms |
212 KB |
n = 32 |
8 |
Correct |
1 ms |
212 KB |
n = 32 |
9 |
Correct |
1 ms |
212 KB |
n = 32 |
10 |
Correct |
1 ms |
308 KB |
n = 32 |
11 |
Correct |
1 ms |
304 KB |
n = 32 |
12 |
Correct |
1 ms |
212 KB |
n = 32 |
13 |
Correct |
1 ms |
212 KB |
n = 32 |
14 |
Correct |
1 ms |
212 KB |
n = 32 |
15 |
Correct |
1 ms |
212 KB |
n = 32 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
n = 32 |
2 |
Correct |
0 ms |
212 KB |
n = 32 |
3 |
Correct |
0 ms |
212 KB |
n = 32 |
4 |
Correct |
1 ms |
308 KB |
n = 32 |
5 |
Correct |
1 ms |
212 KB |
n = 32 |
6 |
Correct |
1 ms |
312 KB |
n = 32 |
7 |
Correct |
1 ms |
212 KB |
n = 32 |
8 |
Correct |
1 ms |
304 KB |
n = 32 |
9 |
Correct |
1 ms |
308 KB |
n = 32 |
10 |
Correct |
1 ms |
212 KB |
n = 32 |
11 |
Correct |
1 ms |
212 KB |
n = 32 |
12 |
Correct |
1 ms |
308 KB |
n = 32 |
13 |
Correct |
1 ms |
340 KB |
n = 32 |
14 |
Correct |
1 ms |
212 KB |
n = 32 |
15 |
Correct |
1 ms |
212 KB |
n = 32 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
500 KB |
n = 128 |
2 |
Correct |
1 ms |
468 KB |
n = 128 |
3 |
Correct |
1 ms |
432 KB |
n = 128 |
4 |
Correct |
1 ms |
468 KB |
n = 128 |
5 |
Correct |
1 ms |
440 KB |
n = 128 |
6 |
Correct |
1 ms |
468 KB |
n = 128 |
7 |
Correct |
1 ms |
400 KB |
n = 128 |
8 |
Correct |
2 ms |
468 KB |
n = 128 |
9 |
Correct |
1 ms |
468 KB |
n = 128 |
10 |
Correct |
1 ms |
468 KB |
n = 128 |
11 |
Correct |
2 ms |
436 KB |
n = 128 |
12 |
Correct |
1 ms |
468 KB |
n = 128 |
13 |
Correct |
1 ms |
468 KB |
n = 128 |
14 |
Correct |
1 ms |
468 KB |
n = 128 |
15 |
Correct |
1 ms |
432 KB |
n = 128 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
n = 128 |
2 |
Correct |
1 ms |
468 KB |
n = 128 |
3 |
Correct |
1 ms |
436 KB |
n = 128 |
4 |
Correct |
1 ms |
436 KB |
n = 128 |
5 |
Correct |
1 ms |
468 KB |
n = 128 |
6 |
Correct |
1 ms |
440 KB |
n = 128 |
7 |
Correct |
1 ms |
468 KB |
n = 128 |
8 |
Correct |
1 ms |
436 KB |
n = 128 |
9 |
Correct |
1 ms |
468 KB |
n = 128 |
10 |
Correct |
2 ms |
468 KB |
n = 128 |
11 |
Correct |
1 ms |
468 KB |
n = 128 |
12 |
Correct |
2 ms |
468 KB |
n = 128 |
13 |
Correct |
1 ms |
468 KB |
n = 128 |
14 |
Correct |
2 ms |
468 KB |
n = 128 |
15 |
Correct |
1 ms |
468 KB |
n = 128 |