Submission #908463

#TimeUsernameProblemLanguageResultExecution timeMemory
908463shoryu386Coreputer (IOI23_coreputer)C++17
80 / 100
1 ms600 KiB
#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-1; 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; 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; } 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; } 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; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...