#include <bits/stdc++.h>
#define pb push_back
#include <vector>
using namespace std;
#ifdef DEBUGGING
#include "../debug.h"
#else
#define debug(x...) void(42)
#endif
#include "messy.h"
vector<int> p;
static inline bool inv(vector<int>& v, int val)
{
auto it = lower_bound(v.begin(), v.end(), val);
return it != v.end() && *it == val;
}
void add(int l, int r, string& s)
{
if (r - l == 1)
return;
int m = l+r>>1;
for (int i = l; i < m; i++)
{
s[i] = '1';
debug(l, r, i, s.c_str());
add_element(s);
s[i] = '0';
}
for (int i = m; i < r; i++)
s[i] = '1';
add(l, m, s);
for (int i = 0; i < m; i++)
s[i] = '1';
for (int i = m; i < r; i++)
s[i] = '0';
add(m, r, s);
}
void find(int l, int r, string& s, vector<int>& cp)
{
if (r - l == 1)
{
assert(cp.size() == 1);
p[cp[0]] = l;
return;
}
vector<int> lp;
for (int i : cp)
{
s[i] = '1';
if (check_element(s))
lp.pb(i);
s[i] = '0';
}
vector<int> rp;
for (int i : cp)
if (!inv(lp, i))
rp.pb(i);
int m = l+r>>1;
for (int i : rp)
s[i] = '1';
find(l, m, s, lp);
for (int i : lp)
s[i] = '1';
for (int i : rp)
s[i] = '0';
find(m, r, s, rp);
for (int i : lp)
s[i] = '0';
}
vector<int> restore_permutation(int n, int w, int r)
{
string s(n, '0');
add(0, n, s);
compile_set();
p = vector<int>(n);
vector<int> cp(n);
for (int i = 0; i < n; i++)
cp[i] = i;
for (int i : cp)
s[i] = '0';
find(0, n, s, cp);
return p;
}
Compilation message
messy.cpp: In function 'void add(int, int, std::string&)':
messy.cpp:26:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
26 | int m = l+r>>1;
| ~^~
messy.cpp: In function 'void find(int, int, std::string&, std::vector<int>&)':
messy.cpp:64:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
64 | int m = l+r>>1;
| ~^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
n = 8 |
2 |
Correct |
1 ms |
252 KB |
n = 8 |
3 |
Correct |
1 ms |
300 KB |
n = 8 |
4 |
Correct |
1 ms |
212 KB |
n = 8 |
5 |
Correct |
0 ms |
212 KB |
n = 8 |
6 |
Correct |
1 ms |
300 KB |
n = 8 |
7 |
Correct |
1 ms |
212 KB |
n = 8 |
8 |
Correct |
1 ms |
296 KB |
n = 8 |
9 |
Correct |
0 ms |
212 KB |
n = 8 |
10 |
Correct |
0 ms |
212 KB |
n = 8 |
11 |
Correct |
0 ms |
212 KB |
n = 8 |
12 |
Correct |
1 ms |
296 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 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
n = 32 |
2 |
Correct |
1 ms |
304 KB |
n = 32 |
3 |
Correct |
1 ms |
300 KB |
n = 32 |
4 |
Correct |
0 ms |
296 KB |
n = 32 |
5 |
Correct |
1 ms |
212 KB |
n = 32 |
6 |
Correct |
0 ms |
296 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 |
# |
결과 |
실행 시간 |
메모리 |
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 |
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 |
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 |
300 KB |
n = 32 |
15 |
Correct |
1 ms |
212 KB |
n = 32 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
468 KB |
n = 128 |
2 |
Correct |
1 ms |
428 KB |
n = 128 |
3 |
Correct |
1 ms |
468 KB |
n = 128 |
4 |
Correct |
1 ms |
468 KB |
n = 128 |
5 |
Correct |
1 ms |
468 KB |
n = 128 |
6 |
Correct |
1 ms |
468 KB |
n = 128 |
7 |
Correct |
1 ms |
468 KB |
n = 128 |
8 |
Correct |
1 ms |
428 KB |
n = 128 |
9 |
Correct |
1 ms |
468 KB |
n = 128 |
10 |
Correct |
1 ms |
468 KB |
n = 128 |
11 |
Correct |
2 ms |
468 KB |
n = 128 |
12 |
Correct |
2 ms |
424 KB |
n = 128 |
13 |
Correct |
1 ms |
468 KB |
n = 128 |
14 |
Correct |
1 ms |
468 KB |
n = 128 |
15 |
Correct |
1 ms |
468 KB |
n = 128 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
468 KB |
n = 128 |
2 |
Correct |
1 ms |
468 KB |
n = 128 |
3 |
Correct |
1 ms |
408 KB |
n = 128 |
4 |
Correct |
1 ms |
468 KB |
n = 128 |
5 |
Correct |
1 ms |
468 KB |
n = 128 |
6 |
Correct |
1 ms |
468 KB |
n = 128 |
7 |
Correct |
1 ms |
432 KB |
n = 128 |
8 |
Correct |
1 ms |
468 KB |
n = 128 |
9 |
Correct |
2 ms |
424 KB |
n = 128 |
10 |
Correct |
1 ms |
468 KB |
n = 128 |
11 |
Correct |
2 ms |
468 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 |
468 KB |
n = 128 |