Submission #925822

#	Time	Username	Problem	Language	Result	Execution time	Memory
925822		Alcabel	cmp (balkan11_cmp)	C++17	100 / 100	3067 ms	107096 KiB

cmp

#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;
}*/

• Subtask 1: 100 / 100