#include <vector>
#include <iostream>
#include "messy.h"
using namespace std;
int calc(int i, int j)
{
//i를 j번 비트까지 봤을 때
int ans = 0;
for (int k = 6; k >= j; k--) ans += i & 1 << k;
return ans;
}
std::vector<int> restore_permutation(int n, int w, int r) {
string s(n, '0');
for (int i = 0; i <= 6; i++) {
s[i] = '1';
add_element(s);
s[i] = '0';
}
for (int i = 1; i < n; i++) s[i] = '1';
add_element(s);
for (int i = 1; i < n; i++) s[i] = '0';
s[0] = '1';
for (int i = 1; i <= 5; i++) {
s[i] = '1';
add_element(s);
}
for (int i = 0; i <= 6; i++) s[i] = '0';
for (int i = 7; i < n; i++) {
for (int j = 0; j < 7; j++) {
if (i & (1 << j)) {
s[i] = '1';
s[j] = '1';
add_element(s);
s[i] = '0';
s[j] = '0';
}
}
}
compile_set();
vector<int> p(n, -1);
vector<int> lst;
//일단 처음에 1인 애들을 다 찾으면 얘녜 p[i] = 0, 1, ..., 6임
for (int i = 0; i < n; i++) {
s[i] = '1';
if (check_element(s)) {
lst.push_back(i);
}
s[i] = '0';
}
vector<int> rev(n);
for (int i = 0; i < 7; i++) {
for (int j = 0; j < n; j++) {
if (lst[i] != j) s[j] = '1';
}
if (check_element(s)) {
rev[0] = lst[i];
p[lst[i]] = 0;
}
for (int j = 0; j < n; j++) s[j] = '0';
}
s[rev[0]] = '1';
for (int i = 1; i <= 5; i++) {
//i번째 거 알아내기: 지금까지
for (int j = 0; j < 7; j++) {
if (p[lst[j]] != -1) continue;
//j인지 테스트
s[lst[j]] = '1';
if (check_element(s)) {
rev[i] = lst[j];
p[lst[j]] = i;
}
s[lst[j]] = '0';
}
s[rev[i]] = '1';
}
for (int j = 0; j < 7; j++) {
if (p[lst[j]] == -1) {
p[lst[j]] = 6;
rev[6] = lst[j];
}
}
for (int i = 0; i < n; i++) s[i] = '0';
//이제 0부터 6번까지를 다 구함
vector<vector<int>> cnt(7, vector<int>(128));
//i가 등장했는가 여부: rev[i] 체크
//cnt[i][j]: i번 비트까지 봤을 때 j인 것이 몇 개인가
//ouc[i][j]: i번 비트까지 봤을 때 j인 것이 몇 개 나왔는가, 로 갈게요
for (int i = 7; i < n; i++) {
for (int k = 6; k >= 0; k--) cnt[k][calc(i, k)]++;
}
for (int i = 0; i < n; i++) {
if (p[i] != -1) continue;
int ret = 0;
for (int k = 6; k >= 0; k--) {
if (cnt[k][ret+(1<<k)] == 0) {
//비트 1 확정
cnt[k][ret]--;
}
else if (cnt[k][ret] == 0) {
ret += (1<<k);
cnt[k][ret]--;
}
else {
s[i] = '1';
s[rev[k]] = '1';
if (check_element(s)) {
ret += (1<<k);
cnt[k][ret]--;
}
else {
cnt[k][ret]--;
}
s[i] = '0';
s[rev[k]] = '0';
}
//k번째 비트까지 봤을 때 ret + (1 << k)인 것의 개수가 0개 남았거나
//k번째 비트까지 봤을 때 ret인 것의 개수가 0개 남았는지 체크
}
//i번의 원래 번호가 ret였다
rev[ret] = i;
p[i] = ret;
}
return p;
}
