#include <bits/stdc++.h>
#include "coreputer.h"
using namespace std;
using ll = long long;
#define MAXN (1000005)
vector<int> malfunctioning_cores(int N) {
ll high = N - 1;
ll low = -1;
while(high - low > 1){ //binary search for leftmost position such that prefix sum of malfunctioning cores > half of total malfunctioning cores
ll mid = (high + low) / 2;
vector<int> T;
for(ll i = 0;i <= mid;i++){
T.push_back(i);
}
ll a = run_diagnostic(T);
if(a == 1){
high = mid;
}else{
low = mid;
}
}
ll checked = 1;
ll parity = 0; //parity of total number of malfunctioning cores
vector<ll> malfunctioning;
malfunctioning.push_back(high);
if(high == N - 1){ //hard code this case (from 0 to N - 2, there are total of 0 or 1 malfunctioning cores)
vector<int> T;
T.push_back(high);
if(run_diagnostic(T) == 0){ //there is 1 malfunctioning core among 0 to N - 2
ll Lb = 0, Ub = N - 2;
while(Lb != Ub){
ll mid = (Lb + Ub) / 2;
T.clear();
for(ll i = Lb;i <= mid;i++){
T.push_back(i);
}
if(run_diagnostic(T) == 0){
Ub = mid;
}else{
Lb = mid + 1;
}
}
malfunctioning.push_back(Lb);
}
}else{
for(ll i = 0;i < high;i++){
if(checked == 15){
if((ll(malfunctioning.size()) % 2) == parity){
checked++;
}else{
checked++;
malfunctioning.push_back(i);
}
break;
}
vector<int> T;
for(ll j = 0;j <= high;j++){
if(i == j) continue;
T.push_back(j);
}
ll a = run_diagnostic(T);
if(a == 0){
parity = 0;
malfunctioning.push_back(i);
}else if(a == -1){
parity = 1;
malfunctioning.push_back(i);
}
checked++;
}
for(ll i = high + 1;i < N && ll(malfunctioning.size()) >= 2;i++){
if(checked == 15){
if((ll(malfunctioning.size()) % 2) == parity){
checked++;
}else{
checked++;
malfunctioning.push_back(i);
}
break;
}
vector<int> T;
for(ll j = high;j < N;j++){
if(i == j) continue;
T.push_back(j);
}
ll a = run_diagnostic(T);
if(a == -1){
malfunctioning.push_back(i);
}
checked++;
}
}
vector<int> ans;
for(ll i = 0;i < N;i++){
ans.push_back(0);
}
for(auto u : malfunctioning){
ans[u] = 1;
}
return ans;
}
