#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();
}
int firstZero = -1, lastZero = -1;
/*
for (int m = 0; m < N; m++){
vector<int> bruh;
for (int y = 0; y <= m; y++) bruh.push_back(y);
int res = run_diagnostic(bruh);
cout << res << " ";
}
cout << "!!!\n";
for (int m = 0; m < N; m++){
vector<int> bruh;
for (int y = m; y < N; y++) bruh.push_back(y);
int res = run_diagnostic(bruh);
cout << res << " ";
}
cout << "!!!\n";
*/
int l = 0, r = 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 = run_diagnostic(bruh);
//cerr << m << ' ' << run_diagnostic(bruh) << "???\n" ;
if (res == 1){
r = m-1;
}
else if (res == 0){
r = m-1;
firstZero = m;
}
else{
l = m+1;
}
}
if (firstZero != -1){
l = 0, 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 = run_diagnostic(bruh);
//cerr << m << ' ' << run_diagnostic(bruh) << "???\n" ;
if (res == 1){
l = m+1;
}
else if (res == 0){
l = m+1;
lastZero = m;
}
else{
r = m-1;
}
}
}
if (firstZero != -1){
//even case
//cerr << firstZero << ' ' << lastZero << '\n';
//our malfunctions are at firstZero, and lastZero
//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(N, 0);
ans[firstZero] = 1;
ans[lastZero] = 1;
for (int x = N-1; x > lastZero; 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(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(lastZero, N-1);
ADDRANGE(x, x);
int res = run_diagnostic(cur);
if (res == 0){
ans[x] = 0;
}
else ans[x] = 1;
}
return ans;
}
else{
//lastOne and firstNegOne+1 are now our checkpoints
vector<int> ans(N, 0);
int lastOne = -1;
int l = 0, 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 = run_diagnostic(bruh);
//cerr << m << ' ' << run_diagnostic(bruh) << "???\n" ;
if (res == 1){
l = m+1;
lastOne = m;
}
else{
r = m-1;
}
}
ans[lastOne] = 1;
//cerr << "fixed pt: " << lastOne << '\n';
for (int x = 0; x < lastOne; 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, lastOne);
cur.erase(find(cur.begin(), cur.end(), x));
int res = run_diagnostic(cur);
if (res != 1){
ans[x] = 1;
}
else ans[x] = 0;
}
for (int x = lastOne+1; x < N; 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(lastOne, N-1);
cur.erase(find(cur.begin(), cur.end(), x));
int res = run_diagnostic(cur);
if (res != 1){
ans[x] = 1;
}
else ans[x] = 0;
}
return ans;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
1 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 KB |
Output is correct |
| 6 |
Correct |
1 ms |
344 KB |
Output is correct |
| 7 |
Correct |
0 ms |
344 KB |
Output is correct |
| 8 |
Correct |
0 ms |
344 KB |
Output is correct |
| 9 |
Correct |
0 ms |
344 KB |
Output is correct |
| 10 |
Correct |
1 ms |
344 KB |
Output is correct |
| 11 |
Correct |
0 ms |
344 KB |
Output is correct |
| 12 |
Correct |
1 ms |
344 KB |
Output is correct |
| 13 |
Correct |
0 ms |
344 KB |
Output is correct |
| 14 |
Correct |
1 ms |
344 KB |
Output is correct |
| 15 |
Correct |
0 ms |
344 KB |
Output is correct |
| 16 |
Correct |
0 ms |
344 KB |
Output is correct |
| 17 |
Correct |
0 ms |
596 KB |
Output is correct |
| 18 |
Correct |
1 ms |
344 KB |
Output is correct |
| 19 |
Correct |
0 ms |
344 KB |
Output is correct |
| 20 |
Partially correct |
1 ms |
344 KB |
Output is partially correct |
| 21 |
Partially correct |
1 ms |
344 KB |
Output is partially correct |
| 22 |
Partially correct |
0 ms |
344 KB |
Output is partially correct |
| 23 |
Partially correct |
0 ms |
344 KB |
Output is partially correct |
| 24 |
Partially correct |
1 ms |
344 KB |
Output is partially correct |
| 25 |
Partially correct |
1 ms |
344 KB |
Output is partially correct |
| 26 |
Partially correct |
0 ms |
344 KB |
Output is partially correct |
| 27 |
Partially correct |
0 ms |
344 KB |
Output is partially correct |
| 28 |
Partially correct |
1 ms |
344 KB |
Output is partially correct |
| 29 |
Partially correct |
1 ms |
344 KB |
Output is partially correct |
| 30 |
Partially correct |
0 ms |
344 KB |
Output is partially correct |
| 31 |
Partially correct |
1 ms |
344 KB |
Output is partially correct |
| 32 |
Partially correct |
1 ms |
344 KB |
Output is partially correct |
| 33 |
Partially correct |
0 ms |
344 KB |
Output is partially correct |
| 34 |
Partially correct |
1 ms |
416 KB |
Output is partially correct |
| 35 |
Partially correct |
1 ms |
344 KB |
Output is partially correct |
| 36 |
Partially correct |
1 ms |
344 KB |
Output is partially correct |
| 37 |
Partially correct |
0 ms |
344 KB |
Output is partially correct |
| 38 |
Partially correct |
1 ms |
344 KB |
Output is partially correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 ms |
344 KB |
Output is correct |
| 4 |
Correct |
1 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 KB |
Output is correct |
| 6 |
Correct |
0 ms |
344 KB |
Output is correct |
| 7 |
Correct |
1 ms |
344 KB |
Output is correct |
| 8 |
Correct |
0 ms |
344 KB |
Output is correct |
| 9 |
Correct |
1 ms |
344 KB |
Output is correct |
| 10 |
Correct |
0 ms |
344 KB |
Output is correct |
| 11 |
Correct |
0 ms |
344 KB |
Output is correct |
| 12 |
Correct |
0 ms |
344 KB |
Output is correct |
| 13 |
Correct |
1 ms |
344 KB |
Output is correct |
| 14 |
Correct |
0 ms |
344 KB |
Output is correct |
| 15 |
Correct |
1 ms |
344 KB |
Output is correct |
| 16 |
Correct |
0 ms |
344 KB |
Output is correct |
| 17 |
Correct |
1 ms |
344 KB |
Output is correct |
| 18 |
Correct |
0 ms |
344 KB |
Output is correct |
| 19 |
Correct |
0 ms |
344 KB |
Output is correct |
| 20 |
Correct |
0 ms |
596 KB |
Output is correct |
| 21 |
Correct |
1 ms |
344 KB |
Output is correct |
| 22 |
Correct |
0 ms |
344 KB |
Output is correct |
| 23 |
Partially correct |
1 ms |
344 KB |
Output is partially correct |
| 24 |
Partially correct |
1 ms |
344 KB |
Output is partially correct |
| 25 |
Partially correct |
0 ms |
344 KB |
Output is partially correct |
| 26 |
Partially correct |
0 ms |
344 KB |
Output is partially correct |
| 27 |
Partially correct |
1 ms |
344 KB |
Output is partially correct |
| 28 |
Partially correct |
1 ms |
344 KB |
Output is partially correct |
| 29 |
Partially correct |
0 ms |
344 KB |
Output is partially correct |
| 30 |
Partially correct |
0 ms |
344 KB |
Output is partially correct |
| 31 |
Partially correct |
1 ms |
344 KB |
Output is partially correct |
| 32 |
Partially correct |
1 ms |
344 KB |
Output is partially correct |
| 33 |
Partially correct |
0 ms |
344 KB |
Output is partially correct |
| 34 |
Partially correct |
1 ms |
344 KB |
Output is partially correct |
| 35 |
Partially correct |
1 ms |
344 KB |
Output is partially correct |
| 36 |
Partially correct |
0 ms |
344 KB |
Output is partially correct |
| 37 |
Partially correct |
1 ms |
416 KB |
Output is partially correct |
| 38 |
Partially correct |
1 ms |
344 KB |
Output is partially correct |
| 39 |
Partially correct |
1 ms |
344 KB |
Output is partially correct |
| 40 |
Partially correct |
0 ms |
344 KB |
Output is partially correct |
| 41 |
Partially correct |
1 ms |
344 KB |
Output is partially correct |
| 42 |
Correct |
0 ms |
344 KB |
Output is correct |
| 43 |
Correct |
0 ms |
344 KB |
Output is correct |
| 44 |
Correct |
0 ms |
344 KB |
Output is correct |
| 45 |
Correct |
0 ms |
344 KB |
Output is correct |
| 46 |
Correct |
1 ms |
344 KB |
Output is correct |
| 47 |
Correct |
0 ms |
344 KB |
Output is correct |
| 48 |
Correct |
0 ms |
344 KB |
Output is correct |
| 49 |
Correct |
0 ms |
344 KB |
Output is correct |
| 50 |
Correct |
0 ms |
344 KB |
Output is correct |
| 51 |
Correct |
1 ms |
344 KB |
Output is correct |
| 52 |
Correct |
1 ms |
344 KB |
Output is correct |
| 53 |
Correct |
1 ms |
344 KB |
Output is correct |
| 54 |
Correct |
0 ms |
344 KB |
Output is correct |
| 55 |
Correct |
1 ms |
344 KB |
Output is correct |
| 56 |
Correct |
0 ms |
344 KB |
Output is correct |
| 57 |
Correct |
1 ms |
344 KB |
Output is correct |
| 58 |
Correct |
0 ms |
344 KB |
Output is correct |
| 59 |
Correct |
0 ms |
344 KB |
Output is correct |
| 60 |
Correct |
1 ms |
344 KB |
Output is correct |
| 61 |
Correct |
1 ms |
344 KB |
Output is correct |
| 62 |
Correct |
1 ms |
344 KB |
Output is correct |
| 63 |
Correct |
1 ms |
344 KB |
Output is correct |
| 64 |
Correct |
0 ms |
344 KB |
Output is correct |
| 65 |
Correct |
0 ms |
344 KB |
Output is correct |
| 66 |
Correct |
0 ms |
344 KB |
Output is correct |
| 67 |
Partially correct |
0 ms |
344 KB |
Output is partially correct |
| 68 |
Partially correct |
0 ms |
344 KB |
Output is partially correct |
| 69 |
Partially correct |
1 ms |
344 KB |
Output is partially correct |
| 70 |
Partially correct |
1 ms |
344 KB |
Output is partially correct |
| 71 |
Partially correct |
1 ms |
344 KB |
Output is partially correct |
| 72 |
Partially correct |
0 ms |
344 KB |
Output is partially correct |
| 73 |
Partially correct |
1 ms |
344 KB |
Output is partially correct |
| 74 |
Partially correct |
0 ms |
344 KB |
Output is partially correct |
| 75 |
Partially correct |
1 ms |
344 KB |
Output is partially correct |
| 76 |
Partially correct |
0 ms |
344 KB |
Output is partially correct |
| 77 |
Partially correct |
1 ms |
344 KB |
Output is partially correct |
| 78 |
Partially correct |
1 ms |
344 KB |
Output is partially correct |
| 79 |
Partially correct |
0 ms |
344 KB |
Output is partially correct |
| 80 |
Partially correct |
1 ms |
344 KB |
Output is partially correct |
| 81 |
Partially correct |
1 ms |
344 KB |
Output is partially correct |
| 82 |
Partially correct |
1 ms |
344 KB |
Output is partially correct |
