# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1034263 | vjudge1 | cmp (balkan11_cmp) | C++17 | 1332 ms | 82576 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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] == 2048) x = 1;
//else if (cnt[1][i] == 2048) 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 time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |