#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;
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
352 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 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 |
1 ms |
596 KB |
Output is correct |
| 12 |
Correct |
0 ms |
344 KB |
Output is correct |
| 13 |
Correct |
1 ms |
344 KB |
Output is correct |
| 14 |
Correct |
1 ms |
344 KB |
Output is correct |
| 15 |
Correct |
1 ms |
344 KB |
Output is correct |
| 16 |
Correct |
1 ms |
596 KB |
Output is correct |
| 17 |
Correct |
0 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 |
1 ms |
344 KB |
Output is correct |
| 21 |
Correct |
0 ms |
344 KB |
Output is correct |
| 22 |
Correct |
1 ms |
344 KB |
Output is correct |
| 23 |
Correct |
0 ms |
344 KB |
Output is correct |
| 24 |
Partially correct |
0 ms |
344 KB |
Output is partially correct |
| 25 |
Correct |
0 ms |
344 KB |
Output is correct |
| 26 |
Correct |
0 ms |
344 KB |
Output is correct |
| 27 |
Correct |
1 ms |
344 KB |
Output is correct |
| 28 |
Correct |
1 ms |
344 KB |
Output is correct |
| 29 |
Correct |
1 ms |
344 KB |
Output is correct |
| 30 |
Partially correct |
0 ms |
344 KB |
Output is partially correct |
| 31 |
Correct |
1 ms |
344 KB |
Output is correct |
| 32 |
Partially correct |
0 ms |
344 KB |
Output is partially correct |
| 33 |
Correct |
1 ms |
344 KB |
Output is correct |
| 34 |
Correct |
1 ms |
344 KB |
Output is correct |
| 35 |
Correct |
1 ms |
340 KB |
Output is correct |
| 36 |
Correct |
1 ms |
344 KB |
Output is correct |
| 37 |
Correct |
0 ms |
344 KB |
Output is correct |
| 38 |
Correct |
1 ms |
344 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
352 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Correct |
1 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 |
1 ms |
596 KB |
Output is correct |
| 15 |
Correct |
0 ms |
344 KB |
Output is correct |
| 16 |
Correct |
1 ms |
344 KB |
Output is correct |
| 17 |
Correct |
1 ms |
344 KB |
Output is correct |
| 18 |
Correct |
1 ms |
344 KB |
Output is correct |
| 19 |
Correct |
1 ms |
596 KB |
Output is correct |
| 20 |
Correct |
0 ms |
344 KB |
Output is correct |
| 21 |
Correct |
0 ms |
344 KB |
Output is correct |
| 22 |
Correct |
0 ms |
344 KB |
Output is correct |
| 23 |
Correct |
1 ms |
344 KB |
Output is correct |
| 24 |
Correct |
0 ms |
344 KB |
Output is correct |
| 25 |
Correct |
1 ms |
344 KB |
Output is correct |
| 26 |
Correct |
0 ms |
344 KB |
Output is correct |
| 27 |
Partially correct |
0 ms |
344 KB |
Output is partially correct |
| 28 |
Correct |
0 ms |
344 KB |
Output is correct |
| 29 |
Correct |
0 ms |
344 KB |
Output is correct |
| 30 |
Correct |
1 ms |
344 KB |
Output is correct |
| 31 |
Correct |
1 ms |
344 KB |
Output is correct |
| 32 |
Correct |
1 ms |
344 KB |
Output is correct |
| 33 |
Partially correct |
0 ms |
344 KB |
Output is partially correct |
| 34 |
Correct |
1 ms |
344 KB |
Output is correct |
| 35 |
Partially correct |
0 ms |
344 KB |
Output is partially correct |
| 36 |
Correct |
1 ms |
344 KB |
Output is correct |
| 37 |
Correct |
1 ms |
344 KB |
Output is correct |
| 38 |
Correct |
1 ms |
340 KB |
Output is correct |
| 39 |
Correct |
1 ms |
344 KB |
Output is correct |
| 40 |
Correct |
0 ms |
344 KB |
Output is correct |
| 41 |
Correct |
1 ms |
344 KB |
Output is correct |
| 42 |
Correct |
1 ms |
340 KB |
Output is correct |
| 43 |
Correct |
0 ms |
344 KB |
Output is correct |
| 44 |
Correct |
0 ms |
344 KB |
Output is correct |
| 45 |
Correct |
1 ms |
344 KB |
Output is correct |
| 46 |
Correct |
1 ms |
344 KB |
Output is correct |
| 47 |
Correct |
1 ms |
344 KB |
Output is correct |
| 48 |
Correct |
1 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 |
0 ms |
344 KB |
Output is correct |
| 52 |
Correct |
0 ms |
344 KB |
Output is correct |
| 53 |
Correct |
0 ms |
344 KB |
Output is correct |
| 54 |
Correct |
1 ms |
344 KB |
Output is correct |
| 55 |
Correct |
1 ms |
344 KB |
Output is correct |
| 56 |
Correct |
1 ms |
344 KB |
Output is correct |
| 57 |
Correct |
1 ms |
344 KB |
Output is correct |
| 58 |
Correct |
1 ms |
344 KB |
Output is correct |
| 59 |
Correct |
1 ms |
344 KB |
Output is correct |
| 60 |
Correct |
0 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 |
1 ms |
344 KB |
Output is correct |
| 66 |
Correct |
0 ms |
344 KB |
Output is correct |
| 67 |
Partially correct |
1 ms |
344 KB |
Output is partially correct |
| 68 |
Partially correct |
1 ms |
600 KB |
Output is partially correct |
| 69 |
Partially correct |
0 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 |
1 ms |
344 KB |
Output is partially correct |
| 73 |
Partially correct |
1 ms |
344 KB |
Output is partially correct |
| 74 |
Partially correct |
1 ms |
344 KB |
Output is partially correct |
| 75 |
Partially correct |
1 ms |
344 KB |
Output is partially correct |
| 76 |
Partially correct |
1 ms |
344 KB |
Output is partially correct |
| 77 |
Partially correct |
1 ms |
344 KB |
Output is partially correct |
| 78 |
Partially correct |
0 ms |
344 KB |
Output is partially correct |
| 79 |
Partially correct |
1 ms |
344 KB |
Output is partially correct |
| 80 |
Partially correct |
1 ms |
344 KB |
Output is partially correct |
| 81 |
Partially correct |
1 ms |
600 KB |
Output is partially correct |
| 82 |
Partially correct |
1 ms |
344 KB |
Output is partially correct |
