#include <vector>
#include <bits/stdc++.h>
#include "messy.h"
#define ll long long
#define f first
#define s second
#define ull unsigned ll
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 128;
string t[nmax * 4];
string xo(string t, string s){
string ans = "";
for(int i= 0; i < t.size(); i++){
if(t[i] == s[i]) ans += '0';
else ans += '1';
}
return ans;
}
int N;
int ans[nmax];
void add_(int l, int r){
if(l == r){
return;
}
string ans;
ans.resize(N);
for(int i = 0; i < N; i++)
ans[i] = '0';
for(int i = 0; i < l - 1; i++)
ans[i] = '1';
for(int i = r; i < N; i++)
ans[i] = '1';
int m = (l + r) / 2;
for(int i = l - 1; i < m; i++){
ans[i] = '1';
add_element(ans);
ans[i] = '0';
}
add_(l, m);
add_(m + 1, r);
}
void ask(int v, int l, int r, string cur){
if(l == r){
for(int i = 0; i < t[v].size(); i++){
if(t[v][i] == '1')
ans[l - 1] = i;
}
return;
}
string qv = cur;
for(int i = 0; i < t[v].size(); i++){
if(t[v][i] == '1'){
qv[i] = '1';
if(check_element(qv))
t[2 * v][i] = '1';
qv[i] = '0';
}
}
t[2 * v + 1] = xo(t[2 * v], t[v]);
int m = (l + r) / 2;
ask(2 * v, l, m, xo(cur, t[v * 2 + 1]));
ask(2 * v + 1, m + 1, r, xo(cur, t[v * 2]));
}
std::vector<int> restore_permutation(int n, int w, int r) {
N = n;
vector <int> an;
for(int i = 0; i <= 4 * n; i++){
for(int j = 0; j < n; ++j)
t[i] += '0';
}
for(int j = 0; j < n; j++)
t[1][j] = '1';
add_(1, n);
compile_set();
ask(1, 1, n, t[0]);
an.resize(n);
for(int i= 0; i < n; i++)
an[ans[i]] = i;
return an;
}
Compilation message
messy.cpp: In function 'std::string xo(std::string, std::string)':
messy.cpp:17:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | for(int i= 0; i < t.size(); i++){
| ~~^~~~~~~~~~
messy.cpp: In function 'void ask(int, int, int, std::string)':
messy.cpp:53:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for(int i = 0; i < t[v].size(); i++){
| ~~^~~~~~~~~~~~~
messy.cpp:60:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for(int i = 0; i < t[v].size(); i++){
| ~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
n = 8 |
2 |
Correct |
1 ms |
212 KB |
n = 8 |
3 |
Correct |
0 ms |
212 KB |
n = 8 |
4 |
Correct |
0 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 |
0 ms |
212 KB |
n = 8 |
11 |
Correct |
1 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 |
312 KB |
n = 8 |
15 |
Correct |
0 ms |
212 KB |
n = 8 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
n = 32 |
2 |
Correct |
1 ms |
340 KB |
n = 32 |
3 |
Correct |
1 ms |
316 KB |
n = 32 |
4 |
Correct |
1 ms |
340 KB |
n = 32 |
5 |
Correct |
1 ms |
340 KB |
n = 32 |
6 |
Correct |
1 ms |
340 KB |
n = 32 |
7 |
Correct |
1 ms |
340 KB |
n = 32 |
8 |
Correct |
1 ms |
340 KB |
n = 32 |
9 |
Correct |
1 ms |
340 KB |
n = 32 |
10 |
Correct |
1 ms |
340 KB |
n = 32 |
11 |
Correct |
1 ms |
312 KB |
n = 32 |
12 |
Correct |
1 ms |
340 KB |
n = 32 |
13 |
Correct |
1 ms |
316 KB |
n = 32 |
14 |
Correct |
1 ms |
316 KB |
n = 32 |
15 |
Correct |
1 ms |
340 KB |
n = 32 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
n = 32 |
2 |
Correct |
1 ms |
312 KB |
n = 32 |
3 |
Correct |
1 ms |
340 KB |
n = 32 |
4 |
Correct |
1 ms |
340 KB |
n = 32 |
5 |
Correct |
1 ms |
340 KB |
n = 32 |
6 |
Correct |
1 ms |
340 KB |
n = 32 |
7 |
Correct |
1 ms |
340 KB |
n = 32 |
8 |
Correct |
1 ms |
340 KB |
n = 32 |
9 |
Correct |
1 ms |
340 KB |
n = 32 |
10 |
Correct |
1 ms |
312 KB |
n = 32 |
11 |
Correct |
1 ms |
340 KB |
n = 32 |
12 |
Correct |
1 ms |
316 KB |
n = 32 |
13 |
Correct |
1 ms |
316 KB |
n = 32 |
14 |
Correct |
1 ms |
340 KB |
n = 32 |
15 |
Correct |
1 ms |
320 KB |
n = 32 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
596 KB |
n = 128 |
2 |
Correct |
2 ms |
572 KB |
n = 128 |
3 |
Correct |
2 ms |
596 KB |
n = 128 |
4 |
Correct |
3 ms |
572 KB |
n = 128 |
5 |
Correct |
2 ms |
596 KB |
n = 128 |
6 |
Correct |
3 ms |
596 KB |
n = 128 |
7 |
Correct |
2 ms |
596 KB |
n = 128 |
8 |
Correct |
3 ms |
640 KB |
n = 128 |
9 |
Correct |
3 ms |
596 KB |
n = 128 |
10 |
Correct |
3 ms |
596 KB |
n = 128 |
11 |
Correct |
2 ms |
596 KB |
n = 128 |
12 |
Correct |
3 ms |
568 KB |
n = 128 |
13 |
Correct |
3 ms |
576 KB |
n = 128 |
14 |
Correct |
2 ms |
596 KB |
n = 128 |
15 |
Correct |
2 ms |
596 KB |
n = 128 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
596 KB |
n = 128 |
2 |
Correct |
3 ms |
600 KB |
n = 128 |
3 |
Correct |
2 ms |
600 KB |
n = 128 |
4 |
Correct |
2 ms |
600 KB |
n = 128 |
5 |
Correct |
3 ms |
600 KB |
n = 128 |
6 |
Correct |
3 ms |
600 KB |
n = 128 |
7 |
Correct |
2 ms |
600 KB |
n = 128 |
8 |
Correct |
3 ms |
600 KB |
n = 128 |
9 |
Correct |
3 ms |
576 KB |
n = 128 |
10 |
Correct |
2 ms |
600 KB |
n = 128 |
11 |
Correct |
2 ms |
600 KB |
n = 128 |
12 |
Correct |
2 ms |
600 KB |
n = 128 |
13 |
Correct |
2 ms |
600 KB |
n = 128 |
14 |
Correct |
2 ms |
600 KB |
n = 128 |
15 |
Correct |
2 ms |
600 KB |
n = 128 |