//In the name of God
#include <bits/stdc++.h>
#include "messy.h"
using namespace std;
typedef int ll;
typedef pair<ll, ll> pll;
#define pb push_back
#define F first
#define S second
#define Mp make_pair
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()
ll n;
void ask(ll l, ll r){
if(r - l == 1) return;
string s;
for(ll i = 0; i < n; i++){
if(l <= i && i < r) s += '0';
else s += '1';
}
ll mid = (l + r) >> 1;
s[l] = '1';
// cout << "? " << s << "\n";
add_element(s);
for(ll i = l + 1; i < mid; i++){
s[i - 1] = '0';
s[i] = '1';
// cout << "? " << s << "\n";
add_element(s);
}
ask(l, mid);
ask(mid, r);
return;
}
vector<ll> solve(ll l, ll r, vector<ll> b){
/*cout << "^ " << l << " " << r << " -> ";
for(ll i : b){
cout << i << " ";
}
cout << "\n";*/
if(r - l == 1) return b;
vector<bool> vis(n);
vector<bool> ok(r - l);
for(ll i : b){
vis[i] = 1;
}
string s;
for(ll i = 0; i < n; i++){
if(!vis[i]) s += '1';
else s += '0';
}
s[b[0]] = '1';
if(check_element(s)) ok[0] = 1;
for(ll i = 1; i < r - l; i++){
s[b[i - 1]] = '0';
s[b[i]] = '1';
if(check_element(s)) ok[i] = 1;
}
ll mid = (l + r) >> 1;
vector<ll> b1, b2;
for(ll i = 0; i < r - l; i++){
if(ok[i]) b1.pb(b[i]);
else b2.pb(b[i]);
}
vector<ll> c1 = solve(l, mid, b1);
vector<ll> c2 = solve(mid, r, b2);
vector<ll> c;
for(ll i : c1){
c.pb(i);
}
for(ll i : c2){
c.pb(i);
}
return c;
}
vector<int> restore_permutation(int N, int w, int r) {
n = N;
ask(0, n);
compile_set();
vector<int> a;
for(ll i = 0; i < n; i++){
a.pb(i);
}
vector<ll> c = solve(0, n, a);
vector<ll> ans(n);
for(ll i = 0; i < n; i++){
ans[c[i]] = i;
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
n = 8 |
2 |
Correct |
1 ms |
204 KB |
n = 8 |
3 |
Correct |
1 ms |
204 KB |
n = 8 |
4 |
Correct |
1 ms |
204 KB |
n = 8 |
5 |
Correct |
1 ms |
204 KB |
n = 8 |
6 |
Correct |
1 ms |
204 KB |
n = 8 |
7 |
Correct |
1 ms |
204 KB |
n = 8 |
8 |
Correct |
1 ms |
204 KB |
n = 8 |
9 |
Correct |
1 ms |
204 KB |
n = 8 |
10 |
Correct |
1 ms |
204 KB |
n = 8 |
11 |
Correct |
1 ms |
204 KB |
n = 8 |
12 |
Correct |
1 ms |
204 KB |
n = 8 |
13 |
Correct |
1 ms |
204 KB |
n = 8 |
14 |
Correct |
0 ms |
204 KB |
n = 8 |
15 |
Correct |
1 ms |
296 KB |
n = 8 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
n = 32 |
2 |
Correct |
1 ms |
204 KB |
n = 32 |
3 |
Correct |
1 ms |
204 KB |
n = 32 |
4 |
Correct |
1 ms |
204 KB |
n = 32 |
5 |
Correct |
1 ms |
292 KB |
n = 32 |
6 |
Correct |
1 ms |
204 KB |
n = 32 |
7 |
Correct |
1 ms |
204 KB |
n = 32 |
8 |
Correct |
1 ms |
204 KB |
n = 32 |
9 |
Correct |
1 ms |
204 KB |
n = 32 |
10 |
Correct |
1 ms |
204 KB |
n = 32 |
11 |
Correct |
1 ms |
204 KB |
n = 32 |
12 |
Correct |
1 ms |
204 KB |
n = 32 |
13 |
Correct |
1 ms |
204 KB |
n = 32 |
14 |
Correct |
1 ms |
204 KB |
n = 32 |
15 |
Correct |
1 ms |
204 KB |
n = 32 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
296 KB |
n = 32 |
2 |
Correct |
1 ms |
204 KB |
n = 32 |
3 |
Correct |
1 ms |
204 KB |
n = 32 |
4 |
Correct |
1 ms |
204 KB |
n = 32 |
5 |
Correct |
1 ms |
256 KB |
n = 32 |
6 |
Correct |
1 ms |
204 KB |
n = 32 |
7 |
Correct |
1 ms |
204 KB |
n = 32 |
8 |
Correct |
1 ms |
204 KB |
n = 32 |
9 |
Correct |
1 ms |
204 KB |
n = 32 |
10 |
Correct |
1 ms |
204 KB |
n = 32 |
11 |
Correct |
1 ms |
204 KB |
n = 32 |
12 |
Correct |
1 ms |
204 KB |
n = 32 |
13 |
Correct |
1 ms |
204 KB |
n = 32 |
14 |
Correct |
1 ms |
204 KB |
n = 32 |
15 |
Correct |
1 ms |
204 KB |
n = 32 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
460 KB |
n = 128 |
2 |
Correct |
2 ms |
460 KB |
n = 128 |
3 |
Correct |
2 ms |
460 KB |
n = 128 |
4 |
Correct |
2 ms |
460 KB |
n = 128 |
5 |
Correct |
2 ms |
460 KB |
n = 128 |
6 |
Correct |
2 ms |
460 KB |
n = 128 |
7 |
Correct |
2 ms |
460 KB |
n = 128 |
8 |
Correct |
2 ms |
416 KB |
n = 128 |
9 |
Correct |
2 ms |
460 KB |
n = 128 |
10 |
Correct |
2 ms |
460 KB |
n = 128 |
11 |
Correct |
2 ms |
460 KB |
n = 128 |
12 |
Correct |
2 ms |
460 KB |
n = 128 |
13 |
Correct |
2 ms |
460 KB |
n = 128 |
14 |
Correct |
2 ms |
460 KB |
n = 128 |
15 |
Correct |
2 ms |
460 KB |
n = 128 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
424 KB |
n = 128 |
2 |
Correct |
2 ms |
460 KB |
n = 128 |
3 |
Correct |
2 ms |
460 KB |
n = 128 |
4 |
Correct |
3 ms |
460 KB |
n = 128 |
5 |
Correct |
2 ms |
460 KB |
n = 128 |
6 |
Correct |
2 ms |
460 KB |
n = 128 |
7 |
Correct |
2 ms |
460 KB |
n = 128 |
8 |
Correct |
2 ms |
428 KB |
n = 128 |
9 |
Correct |
2 ms |
464 KB |
n = 128 |
10 |
Correct |
2 ms |
464 KB |
n = 128 |
11 |
Correct |
2 ms |
460 KB |
n = 128 |
12 |
Correct |
2 ms |
464 KB |
n = 128 |
13 |
Correct |
2 ms |
460 KB |
n = 128 |
14 |
Correct |
2 ms |
460 KB |
n = 128 |
15 |
Correct |
2 ms |
460 KB |
n = 128 |