#include "coreputer.h"
#include <bits/stdc++.h>
std::vector<int> malfunctioning_cores(int N) {
using namespace std;
vector<int> corrupted(N);
int output[N];
int l = 0, r = N-1;
while(l < r){
int mid = (l+r)>>1;
vector<int> v;
for(int i = 0; i <= mid; ++i) v.push_back(i);
if((output[mid] = run_diagnostic(v))>= 0) r = mid;
else l = mid+1;
}
corrupted[l] = 1;
int parity = output[l];
if(l == N-1){
return corrupted;
}
int cnt[2] = {1, 0};
for(int i = 0; i < l; ++i){
vector<int> v;
for(int j = 0; j <= l; ++j) if(j != i) v.push_back(j);
if(run_diagnostic(v) >= 0) corrupted[i] = 0;
else corrupted[i] = 1, cnt[0]++;
}
for(int i = l+1; i < N-1; ++i){
vector<int> v;
if(parity == 1) v.push_back(l); // add l to make the subset size > the other set
for(int j = l+1; j < N; ++j) if(j != i) v.push_back(j);
if(run_diagnostic(v) >= 0) corrupted[i] = 0;
else corrupted[i] = 1, cnt[1]++;
}
if(parity != cnt[0] - cnt[1]) corrupted[N-1] = 1;
else corrupted[N-1] = 0;
return corrupted;
}
