#include <bits/stdc++.h>
#include "messy.h"
using namespace std;
template<typename T>
auto operator<<(ostream &os, T&v)->decltype(v.begin(), os){
os << "[";
int f = 0;
for(auto i:v) {
if(f++)os << ", ";
os << i;
}
os << "]";
return os;
}
template<typename F, typename S>
ostream& operator<<(ostream &os, pair<F, S> const &p) {
return os << "(" << p.first << ", " << p.second << ")";
}
ostream& operator<<(ostream &os, string& s) {
for(char i:s){
os << i;
}
return os;
}
void debug(){}
template<typename T, typename... V>
void debug(T t, V... v) {
cerr << t;
if(sizeof...(v)) {
cerr << ", "; debug(v...);
}
}
#ifdef LOCAL
#define dbg(x...) cerr << "[" << #x << "]: " << "["; debug(x); cerr << "]\n";
#else
#define dbg(x...)
#endif
string s = "";
int na;
vector<int> ans;
void fill(int l, int r, char c) {
for(int i = l;i<=r;i++) {
s[i] = c;
}
}
void add(int l, int r) {
if(l == r)return;
fill(0, na-1, '0');
fill(0, l-1, '1');
fill(r+1, na-1, '1');
int mid = (l+r)/2;
dbg(l, r);
for(int i = l;i<=mid;i++) {
s[i] = '1';
dbg("ADD",s);
add_element(s);
s[i] = '0';
}
add(l, mid);
add(mid+1, r);
}
void solve(vector<int> &v, int l, int r) {
dbg(l, r, v);
if(l == r) {
ans[v[0]] = l;
return;
}
fill(0, na-1, '0');
fill(0, l-1, '1');
fill(r+1, na-1, '1');
int mid = (l+r)>>1ll;
vector<int> left, right;
fill(0, na-1, '1');
for(int i:v)s[i] = '0';
for(int i:v) {
s[i] = '1';
bool check = check_element(s);
dbg(i, s, check);
if(check) {
left.push_back(i);
}
else right.push_back(i);
s[i] = '0';
}
solve(left, l, mid);
solve(right, mid+1, r);
}
vector<int> restore_permutation(int N, int w, int r) {
na = N;
for(int i = 0;i<na;i++)s+="0";
vector<int> v(na);
ans.resize(na);
iota(v.begin(), v.end(), 0);
add(0, na-1);
compile_set();
solve(v, 0, na-1);
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
300 KB |
n = 8 |
2 |
Correct |
1 ms |
300 KB |
n = 8 |
3 |
Correct |
1 ms |
212 KB |
n = 8 |
4 |
Correct |
1 ms |
212 KB |
n = 8 |
5 |
Correct |
1 ms |
340 KB |
n = 8 |
6 |
Correct |
1 ms |
212 KB |
n = 8 |
7 |
Correct |
1 ms |
340 KB |
n = 8 |
8 |
Correct |
1 ms |
212 KB |
n = 8 |
9 |
Correct |
1 ms |
304 KB |
n = 8 |
10 |
Correct |
1 ms |
304 KB |
n = 8 |
11 |
Correct |
1 ms |
212 KB |
n = 8 |
12 |
Correct |
1 ms |
296 KB |
n = 8 |
13 |
Correct |
1 ms |
300 KB |
n = 8 |
14 |
Correct |
1 ms |
300 KB |
n = 8 |
15 |
Correct |
1 ms |
212 KB |
n = 8 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
n = 32 |
2 |
Correct |
1 ms |
212 KB |
n = 32 |
3 |
Correct |
1 ms |
212 KB |
n = 32 |
4 |
Correct |
1 ms |
292 KB |
n = 32 |
5 |
Correct |
1 ms |
212 KB |
n = 32 |
6 |
Correct |
1 ms |
212 KB |
n = 32 |
7 |
Correct |
1 ms |
300 KB |
n = 32 |
8 |
Correct |
1 ms |
212 KB |
n = 32 |
9 |
Correct |
1 ms |
212 KB |
n = 32 |
10 |
Correct |
1 ms |
212 KB |
n = 32 |
11 |
Correct |
1 ms |
212 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 |
1 ms |
296 KB |
n = 32 |
3 |
Correct |
1 ms |
220 KB |
n = 32 |
4 |
Correct |
1 ms |
212 KB |
n = 32 |
5 |
Correct |
1 ms |
320 KB |
n = 32 |
6 |
Correct |
1 ms |
304 KB |
n = 32 |
7 |
Correct |
1 ms |
212 KB |
n = 32 |
8 |
Correct |
1 ms |
212 KB |
n = 32 |
9 |
Correct |
1 ms |
296 KB |
n = 32 |
10 |
Correct |
1 ms |
300 KB |
n = 32 |
11 |
Correct |
1 ms |
212 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 |
2 ms |
468 KB |
n = 128 |
2 |
Correct |
1 ms |
424 KB |
n = 128 |
3 |
Correct |
2 ms |
468 KB |
n = 128 |
4 |
Correct |
2 ms |
468 KB |
n = 128 |
5 |
Correct |
2 ms |
468 KB |
n = 128 |
6 |
Correct |
2 ms |
468 KB |
n = 128 |
7 |
Correct |
2 ms |
468 KB |
n = 128 |
8 |
Correct |
2 ms |
468 KB |
n = 128 |
9 |
Correct |
2 ms |
468 KB |
n = 128 |
10 |
Correct |
2 ms |
428 KB |
n = 128 |
11 |
Correct |
1 ms |
428 KB |
n = 128 |
12 |
Correct |
1 ms |
468 KB |
n = 128 |
13 |
Correct |
1 ms |
468 KB |
n = 128 |
14 |
Correct |
1 ms |
424 KB |
n = 128 |
15 |
Correct |
1 ms |
468 KB |
n = 128 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
n = 128 |
2 |
Correct |
2 ms |
424 KB |
n = 128 |
3 |
Correct |
2 ms |
468 KB |
n = 128 |
4 |
Correct |
2 ms |
468 KB |
n = 128 |
5 |
Correct |
1 ms |
468 KB |
n = 128 |
6 |
Correct |
2 ms |
468 KB |
n = 128 |
7 |
Correct |
1 ms |
468 KB |
n = 128 |
8 |
Correct |
2 ms |
468 KB |
n = 128 |
9 |
Correct |
2 ms |
468 KB |
n = 128 |
10 |
Correct |
1 ms |
432 KB |
n = 128 |
11 |
Correct |
2 ms |
424 KB |
n = 128 |
12 |
Correct |
2 ms |
468 KB |
n = 128 |
13 |
Correct |
2 ms |
468 KB |
n = 128 |
14 |
Correct |
1 ms |
468 KB |
n = 128 |
15 |
Correct |
1 ms |
468 KB |
n = 128 |