Submission #648719

#	Time	Username	Problem	Language	Result	Execution time	Memory
648719		Johann	cmp (balkan11_cmp)	C++14	91 / 100	1834 ms	82452 KiB

cmp

#include "cmp.h"

#include "bits/stdc++.h"
using namespace std;

typedef vector<int> vi;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

const int BASE = 8;
const int LOG = ceil(log(4095) / log(BASE));
vi getDig(int x)
{
    vi ans(LOG, 0);
    for (int i = 0; i < LOG; ++i)
    {
        ans[i] = x % BASE;
        x /= BASE;
    }
    return ans;
}

int addr(int pos, int digit)
{
    return digit * LOG + pos + 1;
}
void print(vi &digits)
{
    for (int d : digits)
        printf("%d ", d);
    printf("\n");
}

void remember(int n)
{
    vi digits = getDig(n);
    // print(ternary);
    for (int i = 0; i < LOG; ++i)
        bit_set(addr(i, digits[i]));
}

int compare(int b)
{
    vi digits = getDig(b);
    // print(ternary);
    for (int i = LOG - 1; i >= 0; --i)
    {
        if (bit_get(addr(i, digits[i])))
            continue;
        if (digits[i] < BASE - digits[i])
        { // untere Hälfte checken...
            for (int d = 0; d < digits[i]; ++d)
            {
                if (bit_get(addr(i, d)))
                    return 1;
            }
            return -1;
        }
        else
        {
            for (int d = BASE - 1; d > digits[i]; --d)
            {
                if (bit_get(addr(i, d)))
                    return -1;
            }
            return 1;
        }
    }
    return 0;
}

• Subtask 1: 91 / 100