// AM+DG
/*
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
#define L(i, varmn, varmx) for(ll i = varmn; i < varmx; i++)
#define LR(i, varmx, varmn) for(ll i = varmx; i > varmn; i--)
#define LI(i, varmn, varmx) for(int i = varmn; i < varmx; i++)
#define LIR(i, varmx, varmn) for(int i = varmx; i > varmn; i--)
#define pb push_back
#include "messy.h"
// #define DEBUG
string to_binstring(int num, int n) {
string res;
LI(i, 0, n) {
res.pb(((num >> i) & 0b1 ? '1' : '0'));
}
assert((int)res.size() == n);
return res;
}
vi subtasks12(int n, int w, int r) {
LI(i, 0, n + 1) {
// Construct a string with this many zeros
string elem;
LI(j, 0, i) {
elem.pb('1');
}
LI(j, i, n) {
elem.pb('0');
}
add_element(elem);
}
compile_set();
int cur_mask = 0;
vi ans(n, 0);
LI(i, 0, n) {
LI(j, 0, n) {
if(((cur_mask >> j) & 0b1) == 0) {
if(check_element(to_binstring(cur_mask | (1 << j), n))) {
// We found the next bitpos
cur_mask |= (1 << j);
ans[j] = i;
break;
}
}
}
}
return ans;
}
vi subtask3(int n, int w, int r) {
// Meet in the middle
LI(i, 1, (n >> 1) + 1) {
string elem;
LI(j, 0, i - 1) {
elem.pb('0');
}
elem.pb('1');
LI(j, i, n) {
elem.pb('0');
}
add_element(elem);
}
LI(i, 0, (n >> 1)) {
string elem(n, '1');
LI(j, n >> 1, n) {
elem[j] = '0';
}
elem[i] = '0';
if(i > 0) elem[i - 1] = '0';
add_element(elem);
}
LI(i, 0, (n >> 1)) {
string elem(n, '1');
LI(j, 0, n >> 1) {
elem[j] = '0';
}
elem[i + (n >> 1)] = '0';
if(i > 0) elem[i + (n >> 1) - 1] = '0';
add_element(elem);
}
compile_set();
int cur_mask = 0;
vi ans(n, 0);
// Iterate, finding the ones with popcount 1
vi is_pc1(n, false);
int pc1mask = 0;
LI(j, 0, n) {
if(check_element(to_binstring(1 << j, n))) {
is_pc1[j] = true;
pc1mask |= 1 << j;
}
}
vi found(n, false);
int first_left_bit;
LI(j, 0, n) {
if(is_pc1[j] && check_element(to_binstring(pc1mask ^ (1 << j), n))) {
first_left_bit = j;
ans[j] = 0;
found[j] = true;
break;
}
}
int cur_left_mask = pc1mask ^ (1 << first_left_bit);
LI(i, 1, n >> 1) {
LI(j, 0, n >> 1) {
if(is_pc1[j] && !found[j]) {
if(check_element(to_binstring(cur_left_mask ^ (1 << j), n))) {
ans[j] = i;
found[j] = true;
cur_left_mask = ~(1 << j);
}
}
}
}
// Right bit
int first_right_bit;
LI(j, 0, n) {
if(!is_pc1[j] && check_element(to_binstring((~pc1mask) ^ (1 << j), n))) {
first_right_bit = j;
ans[j] = 0;
found[j] = true;
break;
}
}
int cur_right_mask = pc1mask ^ (1 << first_left_bit);
LI(i, 1, n >> 1) {
LI(j, 0, n >> 1) {
if(!is_pc1[j] && !found[j]) {
if(check_element(to_binstring(cur_right_mask ^ (1 << j), n))) {
ans[j] = i;
found[j] = true;
cur_right_mask = ~(1 << j);
}
}
}
}
return ans;
}
vi restore_permutation(int n, int w, int r) {
if((n == 8 && w == 256 && r == 256) || (n == 32 && w == 320 && r == 1024)) return subtasks12(n, w, r);
// else if(n == 32 & w == 1024 && r == 320) return subtask3(n, w, r);
vi nope;
return nope;
}
#ifdef DEBUG
int main() {
}
#endif
Compilation message
messy.cpp: In function 'vi subtask3(int, int, int)':
messy.cpp:120:9: warning: unused variable 'cur_mask' [-Wunused-variable]
120 | int cur_mask = 0;
| ^~~~~~~~
messy.cpp:161:9: warning: variable 'first_right_bit' set but not used [-Wunused-but-set-variable]
161 | int first_right_bit;
| ^~~~~~~~~~~~~~~
messy.cpp:146:38: warning: 'first_left_bit' may be used uninitialized in this function [-Wmaybe-uninitialized]
146 | int cur_left_mask = pc1mask ^ (1 << first_left_bit);
| ~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
n = 8 |
| 2 |
Correct |
0 ms |
348 KB |
n = 8 |
| 3 |
Correct |
0 ms |
344 KB |
n = 8 |
| 4 |
Correct |
0 ms |
348 KB |
n = 8 |
| 5 |
Correct |
0 ms |
436 KB |
n = 8 |
| 6 |
Correct |
0 ms |
348 KB |
n = 8 |
| 7 |
Correct |
0 ms |
348 KB |
n = 8 |
| 8 |
Correct |
0 ms |
344 KB |
n = 8 |
| 9 |
Correct |
0 ms |
348 KB |
n = 8 |
| 10 |
Correct |
0 ms |
348 KB |
n = 8 |
| 11 |
Correct |
0 ms |
348 KB |
n = 8 |
| 12 |
Correct |
0 ms |
348 KB |
n = 8 |
| 13 |
Correct |
0 ms |
348 KB |
n = 8 |
| 14 |
Correct |
0 ms |
348 KB |
n = 8 |
| 15 |
Correct |
0 ms |
348 KB |
n = 8 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
n = 32 |
| 2 |
Correct |
1 ms |
348 KB |
n = 32 |
| 3 |
Correct |
0 ms |
344 KB |
n = 32 |
| 4 |
Correct |
0 ms |
348 KB |
n = 32 |
| 5 |
Correct |
0 ms |
348 KB |
n = 32 |
| 6 |
Correct |
0 ms |
348 KB |
n = 32 |
| 7 |
Correct |
0 ms |
348 KB |
n = 32 |
| 8 |
Correct |
0 ms |
348 KB |
n = 32 |
| 9 |
Correct |
0 ms |
348 KB |
n = 32 |
| 10 |
Correct |
0 ms |
348 KB |
n = 32 |
| 11 |
Correct |
1 ms |
348 KB |
n = 32 |
| 12 |
Correct |
1 ms |
348 KB |
n = 32 |
| 13 |
Correct |
0 ms |
348 KB |
n = 32 |
| 14 |
Correct |
0 ms |
348 KB |
n = 32 |
| 15 |
Correct |
0 ms |
348 KB |
n = 32 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
grader returned WA |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
grader returned WA |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
grader returned WA |
| 2 |
Halted |
0 ms |
0 KB |
- |
