#include "cmp.h"
#include <bits/stdc++.h>
using namespace std;
/*
int arr[10000];
void bit_set(int i) {
arr[i] = 1;
}
int bit_get(int i) {
return arr[i];
}
*/
const int pref[6] = {0, 4, 20, 84, 340, 1364};
int get_hash(int x, int s) {
return pref[s] + (x & ((1 << (2 * s + 2)) - 1));
}
int reverse(int x) {
string s = "";
for (int i = 0; i < 12; ++i) {
if (x & (1 << i)) {
s += '1';
} else {
s += '0';
}
}
reverse(s.begin(), s.end());
int res = 0;
for (int i = 0; i < 12; ++i) {
if (s[i] == '1') {
res |= (1 << i);
}
}
return res;
}
void remember(int a) {
a = reverse(a);
for (int s = 0; s < 6; ++s) {
// first 2s + 2 bits
bit_set(get_hash(a, s) + 1);
}
}
int compare(int b) {
b = reverse(b);
int left = 0, right = 7;
while (right - left > 1) {
int mid = left + (right - left) / 2;
if (bit_get(get_hash(b, mid - 1) + 1)) {
left = mid;
} else {
right = mid;
}
}
if (left == 6) {
return 0;
}
int digit = (b >> (2 * left)) & 3;
if (digit == 0) {
return -1;
}
if (digit == 3) {
return 1;
}
if (digit == 1) {
// real digit = 2, check for 3
if (bit_get(get_hash(b ^ (1 << (2 * left + 1)), left) + 1)) {
return -1;
}
return 1;
}
if (digit == 2) {
// real digit = 1, check for 0
if (bit_get(get_hash(b ^ (1 << (2 * left + 1)), left) + 1)) {
return 1;
}
return -1;
}
assert(false);
}
/*
void solve() {
int a, b;
cin >> a >> b;
remember(a);
cerr << compare(b) << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int T = 1;
cin >> T;
while (T--) {
solve();
cerr << "-----------\n";
cout << "-----------\n";
}
#else
int T = 1;
// cin >> T;
while (T--) {
solve();
}
#endif
return 0;
}*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3067 ms |
107096 KB |
Output is correct - maxAccess = 10, score = 100 |
