Submission #903993

#TimeUsernameProblemLanguageResultExecution timeMemory
903993ItamarCoreputer (IOI23_coreputer)C++17
90 / 100
1 ms600 KiB
#include "coreputer.h" #include <vector> using namespace std; #define vi vector<int> #include <algorithm> #include <map> map<vi, int> m; int run_diagnostici(vi v) { if (m[v])return m[v] - 2; m[v] = 2+run_diagnostic(v); return m[v] - 2; } std::vector<int> malfunctioning_cores(int N) { vi ans(N); int l = 0, r = N-1; vi q; while (q.size()<5) { int mid = (l + r) / 2; vi v; for (int i = 0; i <= mid; i++)v.push_back(i); int a = run_diagnostici(v); q.push_back(a); if (a == 0) { l = mid, r = mid; } if (a == -1)l = mid+1; else r = mid; } int t = q.back(); int f = N - 1; if (l == N - 1) { for (int i = 0; i < N; i++)ans[i] = 0; ans[N - 1] = 1; return ans; } if (N==16&& l == N - 2) { if (t == 0) { ans[N - 2] = 1; ans[N - 1] = 1; return ans; } else if (t == -1) { ans[N - 1] = 1; return ans; } else { ans[N - 2] = 1; } f--; vi v; for (int i = 0; i < N; i++)if (i != N - 2)v.push_back(i); if (run_diagnostic(v) == 0)return v; int li = 0, ri = N - 3; ans[N - 1] = 1; while (li < ri) { int mid = (li + ri) / 2; vi vec; for (int i = 0; i <= mid; i++)vec.push_back(i); vec.push_back(N - 1); if (run_diagnostic(vec))ri = mid; else li = mid + 1; } ans[li] = 1; return ans; } int g=-1; int tt=t; for (int i = 0; i < f; i++) { vi v; for (int j = 0; j <= l; j++)if (i != j && (g!=j || i<=l))v.push_back(j); int a; if (i > l) { v.push_back(i); a = run_diagnostici(v); ans[i] = (tt < a); } else { a = run_diagnostici(v); ans[i] = (t > a); if (ans[i] && t!=0) { g = i; tt = a; } } } int x1=0; for (int i = 0; i < N - 1; i++) { if (ans[i] && i <= l)x1++; else if (ans[i])x1--; } ans[N - 1] = (x1 > (t)); return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...