Submission #1034264

#TimeUsernameProblemLanguageResultExecution timeMemory
1034264vjudge1cmp (balkan11_cmp)C++17
0 / 100
450 ms82764 KiB
#include "cmp.h" #include <bits/stdc++.h> using namespace std; const int inf = INT_MAX; int a[4096], b[2][64], cnt[2][12]; void remember(int n) { for (int i = 0; i < 4096; i++) { a[i] = -2; } for (int i = 0; i < 64; i++) { b[0][i] = inf; b[1][i] = -inf; } for (int i = 0; i < 12; i++) { cnt[0][i] = 0; cnt[1][i] = 0; } int x = __builtin_popcount(n); if (x <= 1 + 12-x) { for (int i = 0; i <= 11; i++) { if ((n >> i) & 1) bit_set(i+1); } } else { bit_set(13); for (int i = 0; i <= 11; i++) { if (!((n >> i) & 1)) bit_set(i+1); } } } void update(int x, int y) { a[x] = y; b[0][x/64] = min(b[0][x/64], y); b[1][x/64] = max(b[1][x/64], y); } int compare(int n) { /* if (n && a[n-1] == -1 && n+1 < 4096 && a[n+1] == 1) { update(n, 0); return 0; } for (int i = 0; i < n; i++) { if (i%64 == 0 && i+63 < n) { if (b[1][i/64] > -1) { update(n, 1); return 1; } i += 63; continue; } if (a[i] == -2) continue; else if (a[i] > -1) { update(n, 1); return 1; } } for (int i = n+1; i < 4096; i++) { if (i%64 == 0) { if (b[0][i/64] < 1) { update(n, -1); return -1; } i += 63; continue; } if (a[i] == -2) continue; else if (a[i] < 1) { update(n, -1); return -1; } } */ int inv = -1; for (int i = 11; i >= 0; i--) { int x; if (cnt[0][i] > 5000) x = 1; else if (cnt[1][i] > 5000) x = 0; else { x = bit_get(i+1); if (inv == -1) inv = bit_get(13); if (inv) x = !x; } if (!x) cnt[0][i]++; else cnt[1][i]++; int y = (n >> i) & 1; if (x > y) { update(n, -1); return -1; } else if (x < y) { update(n, 1); return 1; } } update(n, 0); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...