#include "coreputer.h"
#include <cassert>
#include <cstdio>
#include <string>
#include <vector>
static inline constexpr int maxDiagnostics = 32;
static int diagnostic_counter = 0;
static int malfunctioningCores = 0;
static int N;
static std::vector<int> M;
static inline void protocol_violation(std::string message) {
printf("Protocol Violation: %s\n", message.c_str());
exit(0);
}
int run_diagnostic(std::vector<int> T) {
++diagnostic_counter;
if (diagnostic_counter > maxDiagnostics) {
protocol_violation("too many calls");
}
int l = T.size();
if (l > N) {
protocol_violation("invalid array");
}
for (int i = 0; i < l; ++i) {
if (T[i] < 0 || T[i] >= N) {
protocol_violation("invalid array");
}
for (int j = 0; j < i; ++j) {
if (T[i] == T[j]) {
protocol_violation("invalid array");
}
}
}
int malfunctioningTaggedCores = 0;
for (int i : T) {
if (M[i] == 1) malfunctioningTaggedCores++;
}
int malfunctioningUntaggedCores = malfunctioningCores - malfunctioningTaggedCores;
if (malfunctioningTaggedCores > malfunctioningUntaggedCores) {
return 1;
}
if (malfunctioningTaggedCores == malfunctioningUntaggedCores) {
return 0;
}
return -1;
}
#include "coreputer.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> ntwo(){
int res = run_diagnostic({0});
if (res == 1){
return {1, 0};
}
else if (res == 0){
int any = run_diagnostic({0, 1});
if (any == 0){
return {0, 0};
}
else return {1, 1};
}
else return {0, 1};
}
vector<int> malfunctioning_cores(int N) {
if (N == 2){
return ntwo();
}
//if malfunctioning cores is even
int results[16];
for (int x = 0; x < 16; x++){
vector<int> bruh;
for (int y = 0; y <= x; y++) bruh.push_back(y);
results[x] = run_diagnostic(bruh);
}
int firstZero = -1, lastZero = -1;
for (int x = 0; x < 16; x++){
if (results[x] == 0){
if (firstZero == -1) firstZero = x;
lastZero = x;
}
}
assert(lastZero != -1); //even case
if (firstZero == 0 && lastZero == 15){
return {0, 0, 0, 0,
0, 0, 0, 0,
0, 0, 0, 0,
0, 0, 0, 0};
}
cerr << firstZero << ' ' << lastZero << '\n';
//our malfunctions are at firstZero, and lastZero+1
//we also now know that there are an equal number of malfunctions in the two segments [0, firstZero-1] and [lastZero+2, 15]
vector<int> ans(16, 0);
ans[firstZero] = 1;
ans[lastZero+1] = 1;
for (int x = 15; x > lastZero+1; x--){
//include [0, firstZero], include [lastZero+1, 15], except one element
vector<int> cur;
#define ADDRANGE(a, b) for (int y = a; y <= b; y++) cur.push_back(y);
ADDRANGE(0, firstZero);
//ADDRANGE(lastZero+1, 15);
//cur.erase(find(cur.begin(), cur.end(), x));
ADDRANGE(x, x);
int res = run_diagnostic(cur);
//cerr << "\n run: \n";
//for (auto y : cur) cerr << y << ' ';
//cerr << '\n';
//cerr << res << '\n';
if (res == 0){
ans[x] = 0;
}
else ans[x] = 1;
}
for (int x = 0; x < firstZero; x++){
//include [0, firstZero], exclude [lastZero+1, 15], except one element
vector<int> cur;
#define ADDRANGE(a, b) for (int y = a; y <= b; y++) cur.push_back(y);
//ADDRANGE(0, firstZero);
ADDRANGE(lastZero+1, 15);
ADDRANGE(x, x);
//cur.erase(find(cur.begin(), cur.end(), x));
int res = run_diagnostic(cur);
if (res == 0){
ans[x] = 0;
}
else ans[x] = 1;
}
return ans;
}
int main() {
assert(1 == scanf("%d", &N));
M.resize(N);
for (int i = 0; i < N; ++i) {
assert(1 == scanf("%d", &M[i]));
malfunctioningCores += M[i];
}
if (malfunctioningCores == 0) {
printf("No Malfunctioning Core\n");
exit(0);
}
std::vector<int> c = malfunctioning_cores(N);
int n = c.size();
for (int i = 0; i < n; ++i) {
printf(i == 0 ? "%d" : " %d", c[i]);
}
printf("\n");
printf("%d\n", diagnostic_counter);
return 0;
}
Compilation message
/usr/bin/ld: /tmp/cc4gBAOn.o: in function `run_diagnostic(std::vector<int, std::allocator<int> >)':
stub.cpp:(.text+0xc0): multiple definition of `run_diagnostic(std::vector<int, std::allocator<int> >)'; /tmp/ccfgGolq.o:coreputer.cpp:(.text+0x30): first defined here
/usr/bin/ld: /tmp/cc4gBAOn.o: in function `main':
stub.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccfgGolq.o:coreputer.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
