#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
#include "messy.h"
int lg(int N) {
int curr = 1;
int res = 0;
while (curr < N) {
curr *= 2;
res++;
}
return res;
}
string sor(string x, string y) { // XOR of strings w/ same length
int M = x.size();
string res;
for (int i = 0; i < M; i++) {
if (x[i] == y[i])
res += '0';
else
res += '1';
}
return res;
}
vi restore_permutation(int N, int W, int R) {
int M = lg(N); // power of 2
vector<string> bases(M, string((1 << M), '0'));
for (int i = 1; i < M - 1; i++) {
int upto = (1 << M) - (1 << (M - i)) - 1;
// cout<<i<<": "<<upto<<endl;
for (int j = 0; j <= upto; j++) {
bases[i][j] = '1';
}
}
bases[M - 1] = string((1 << M), '1');
/* cout<<"bases: ";
for (string s : bases)
cout<<s<<" ";
cout<<endl;*/
// get what all ith bit off maps to, then each appears in exactly one
// the val it maps to appears exactly in those where its bit is off
vector<string> tq; // to query
for (int i = M - 1; i >= 0; i--) {
vector<string> ctq; // to query for set i
for (int j = 0; j < (1 << M); j++) {
if ((j & (1 << i)) == 0) {
string rt((1 << M), '0');
rt[j] = '1';
ctq.pb(sor(rt, bases[M - i - 1]));
}
}
/* cout<<i<<": ";
for (string s : ctq)
cout<<s<<" ";
cout<<endl;*/
for (string s : ctq)
tq.pb(s);
}
for (string s : tq)
add_element(s);
compile_set();
vector<vector<bool>> aft(M, vector<bool>((1 << M), false));
// what set i becomes after perm
// set i: all of bit (M - i - 1) are off
string currb((1 << M), '0');
for (int i = 0; i < M; i++) {
// cout<<"at "<<i<<endl;
if (i == M - 1)
currb = string((1 << M), '1');
vi bec;
for (int j = 0; j < (1 << M); j++) {
string rt((1 << M), '0');
rt[j] = '1';
string qr = sor(rt, currb);
// cout<<"asking "<<qr<<endl;
bool res = check_element(qr);
if (res) {
// cout<<"orz"<<endl;
bec.pb(j);
aft[i][j] = true;
}
}
// bec has size (1 << (M - 1))
for (int x : bec)
currb[x] = '1';
}
/* cout<<"aft: "<<endl;
for (int i = 0; i < M; i++) {
cout<<"set "<<i<<": ";
for (int j = 0; j < (1 << M); j++) {
if (aft[i][j])
cout<<1<<" ";
else
cout<<0<<" ";
}
cout<<endl;
}*/
vi ans((1 << M), -1);
for (int i = 0; i < (1 << M); i++) {
for (int j = 0; j < (1 << M); j++) {
bool same = true;
// check if sets of j completely match i's
for (int k = 0; k < M; k++) {
if (aft[M - 1 - k][j] && ((i & (1 << k)) != 0))
same = false;
if (!aft[M - 1 - k][j] && ((i & (1 << k)) == 0))
same = false;
}
if (same) {
ans[j] = i;
}
}
}
/* cout<<"ANSWER: ";
for (int x : ans)
cout<<x<<" ";
cout<<endl;*/
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
n = 8 |
| 2 |
Correct |
0 ms |
432 KB |
n = 8 |
| 3 |
Correct |
0 ms |
348 KB |
n = 8 |
| 4 |
Correct |
0 ms |
348 KB |
n = 8 |
| 5 |
Correct |
0 ms |
344 KB |
n = 8 |
| 6 |
Correct |
0 ms |
344 KB |
n = 8 |
| 7 |
Correct |
0 ms |
348 KB |
n = 8 |
| 8 |
Correct |
0 ms |
348 KB |
n = 8 |
| 9 |
Correct |
0 ms |
348 KB |
n = 8 |
| 10 |
Correct |
0 ms |
348 KB |
n = 8 |
| 11 |
Correct |
0 ms |
600 KB |
n = 8 |
| 12 |
Correct |
0 ms |
348 KB |
n = 8 |
| 13 |
Correct |
0 ms |
604 KB |
n = 8 |
| 14 |
Correct |
0 ms |
348 KB |
n = 8 |
| 15 |
Correct |
0 ms |
436 KB |
n = 8 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
n = 32 |
| 2 |
Correct |
1 ms |
344 KB |
n = 32 |
| 3 |
Correct |
1 ms |
348 KB |
n = 32 |
| 4 |
Correct |
1 ms |
504 KB |
n = 32 |
| 5 |
Correct |
1 ms |
348 KB |
n = 32 |
| 6 |
Correct |
1 ms |
348 KB |
n = 32 |
| 7 |
Correct |
1 ms |
348 KB |
n = 32 |
| 8 |
Correct |
1 ms |
348 KB |
n = 32 |
| 9 |
Correct |
1 ms |
428 KB |
n = 32 |
| 10 |
Correct |
0 ms |
348 KB |
n = 32 |
| 11 |
Correct |
1 ms |
344 KB |
n = 32 |
| 12 |
Correct |
1 ms |
348 KB |
n = 32 |
| 13 |
Correct |
0 ms |
348 KB |
n = 32 |
| 14 |
Correct |
1 ms |
344 KB |
n = 32 |
| 15 |
Correct |
1 ms |
348 KB |
n = 32 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
n = 32 |
| 2 |
Correct |
1 ms |
432 KB |
n = 32 |
| 3 |
Correct |
1 ms |
348 KB |
n = 32 |
| 4 |
Correct |
1 ms |
600 KB |
n = 32 |
| 5 |
Correct |
1 ms |
348 KB |
n = 32 |
| 6 |
Correct |
1 ms |
348 KB |
n = 32 |
| 7 |
Correct |
1 ms |
348 KB |
n = 32 |
| 8 |
Correct |
0 ms |
348 KB |
n = 32 |
| 9 |
Correct |
1 ms |
344 KB |
n = 32 |
| 10 |
Correct |
1 ms |
348 KB |
n = 32 |
| 11 |
Correct |
1 ms |
344 KB |
n = 32 |
| 12 |
Correct |
0 ms |
348 KB |
n = 32 |
| 13 |
Correct |
1 ms |
344 KB |
n = 32 |
| 14 |
Correct |
1 ms |
348 KB |
n = 32 |
| 15 |
Correct |
1 ms |
348 KB |
n = 32 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
600 KB |
n = 128 |
| 2 |
Correct |
2 ms |
600 KB |
n = 128 |
| 3 |
Correct |
3 ms |
604 KB |
n = 128 |
| 4 |
Correct |
2 ms |
496 KB |
n = 128 |
| 5 |
Correct |
4 ms |
712 KB |
n = 128 |
| 6 |
Correct |
2 ms |
856 KB |
n = 128 |
| 7 |
Correct |
2 ms |
716 KB |
n = 128 |
| 8 |
Correct |
2 ms |
604 KB |
n = 128 |
| 9 |
Correct |
2 ms |
604 KB |
n = 128 |
| 10 |
Correct |
2 ms |
860 KB |
n = 128 |
| 11 |
Correct |
3 ms |
604 KB |
n = 128 |
| 12 |
Correct |
2 ms |
692 KB |
n = 128 |
| 13 |
Correct |
3 ms |
688 KB |
n = 128 |
| 14 |
Correct |
2 ms |
604 KB |
n = 128 |
| 15 |
Correct |
2 ms |
604 KB |
n = 128 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
604 KB |
n = 128 |
| 2 |
Correct |
2 ms |
604 KB |
n = 128 |
| 3 |
Correct |
2 ms |
604 KB |
n = 128 |
| 4 |
Correct |
2 ms |
604 KB |
n = 128 |
| 5 |
Correct |
2 ms |
604 KB |
n = 128 |
| 6 |
Correct |
2 ms |
604 KB |
n = 128 |
| 7 |
Correct |
4 ms |
604 KB |
n = 128 |
| 8 |
Correct |
3 ms |
604 KB |
n = 128 |
| 9 |
Correct |
3 ms |
604 KB |
n = 128 |
| 10 |
Correct |
2 ms |
600 KB |
n = 128 |
| 11 |
Correct |
3 ms |
604 KB |
n = 128 |
| 12 |
Correct |
2 ms |
604 KB |
n = 128 |
| 13 |
Correct |
2 ms |
604 KB |
n = 128 |
| 14 |
Correct |
3 ms |
604 KB |
n = 128 |
| 15 |
Correct |
3 ms |
604 KB |
n = 128 |
