#include "coreputer.h"
#include <bits/stdc++.h>
using namespace std;
map<vector<int>, int> dp;
int diag(vector<int> val){
if (dp.count(val) != 0) return dp[val];
else return dp[val] = run_diagnostic(val);
}
vector<int> malfunctioning_cores(int N) {
int firstZero = -1, lastZero = -1;
int l = 0, r = N-2;
int nextR = N-1;
while (l <= r){
int m = (l+r)/2;
vector<int> bruh;
for (int y = 0; y <= m; y++) bruh.push_back(y);
int res = diag(bruh);
if (res == 1){
r = m-1;
nextR = m-1;
}
else if (res == 0){
r = m-1;
firstZero = m;
}
else{
l = m+1;
}
}
if (firstZero != -1){
lastZero = firstZero;
l = firstZero+1;
r = nextR;
while (l <= r){
int m = (l+r)/2;
vector<int> bruh;
for (int y = 0; y <= m; y++) bruh.push_back(y);
int res = diag(bruh);
//cerr << m << ' ' << diag(bruh) << "???\n" ;
if (res == 0){
l = m+1;
lastZero = m;
}
else{
r = m-1;
}
}
lastZero++;
vector<int> ans(N, 0);
ans[firstZero] = 1;
ans[lastZero] = 1;
if (N - lastZero < firstZero){
int cnt = 0;
for (int x = N-1; x > lastZero; x--){
vector<int> cur;
#define ADDRANGE(a, b) for (int y = a; y <= b; y++) cur.push_back(y);
ADDRANGE(0, firstZero);
ADDRANGE(x, x);
int res = diag(cur);
if (res == 0){
ans[x] = 0;
}
else ans[x] = 1, cnt++;
}
vector<int> vec;
for (int x = 0; x < firstZero; x++) vec.push_back(x);
random_shuffle(vec.begin(), vec.end());
int remain = vec.size();
for (auto x : vec){
if (cnt == 0){
ans[x] = 0;
remain--;
continue;
}
if (remain == cnt){
ans[x] = (cnt >= 1); cnt--;
remain--;
continue;
}
vector<int> cur;
ADDRANGE(lastZero, N-1);
ADDRANGE(x, x);
int res = diag(cur);
if (res == 0){
ans[x] = 0;
}
else ans[x] = 1, cnt--;
remain--;
}
}
else{
int cnt = 0;
for (int x = 0; x < firstZero; x++){
vector<int> cur;
ADDRANGE(lastZero, N-1);
ADDRANGE(x, x);
int res = diag(cur);
if (res == 0){
ans[x] = 0;
}
else ans[x] = 1, cnt++;
}
vector<int> vec;
for (int x = lastZero+1; x < N; x++) vec.push_back(x);
random_shuffle(vec.begin(), vec.end());
int remain = vec.size();
for (int x : vec){
vector<int> cur;
if (cnt == 0){
ans[x] = 0;
remain--;
continue;
}
if (remain == cnt){
remain--;
ans[x] = (cnt >= 1); cnt--;
continue;
}
#define ADDRANGE(a, b) for (int y = a; y <= b; y++) cur.push_back(y);
ADDRANGE(0, firstZero);
ADDRANGE(x, x);
int res = diag(cur);
if (res == 0){
ans[x] = 0;
}
else ans[x] = 1, cnt--;
remain--;
}
}
return ans;
}
else{
vector<int> ans(N, 0);
int lastOne = 0;
int l = 1, r = N-1;
while (l <= r){
int m = (l+r)/2;
vector<int> bruh;
for (int y = m; y < N; y++) bruh.push_back(y);
int res = diag(bruh);
//cerr << m << ' ' << diag(bruh) << "???\n" ;
if (res == 1){
l = m+1;
lastOne = m;
}
else{
r = m-1;
}
}
ans[lastOne] = 1;
assert(0 <= lastOne && lastOne < N);
for (int x = 0; x < lastOne; x++){
vector<int> cur;
#define ADDRANGE(a, b) for (int y = a; y <= b; y++) cur.push_back(y);
ADDRANGE(0, lastOne);
cur.erase(find(cur.begin(), cur.end(), x));
int res = diag(cur);
if (res != 1){
ans[x] = 1;
}
else ans[x] = 0;
}
for (int x = lastOne+1; x < N; x++){
vector<int> cur;
ADDRANGE(lastOne, N-1);
cur.erase(find(cur.begin(), cur.end(), x));
int res = diag(cur);
if (res != 1){
ans[x] = 1;
}
else ans[x] = 0;
}
return ans;
}
}
