Submission #412908

#	Time	Username	Problem	Language	Result	Execution time	Memory
412908		thecodingwizard	cmp (balkan11_cmp)	C++11	100 / 100	2573 ms	82496 KiB

cmp

#include "cmp.h"
#include <bits/stdc++.h>

using namespace std;

void remember(int n) {
    vector<int> gaps = { 373, 42, 6, 1 };
    int cur = 0;
    int end = 4096;
    int nxt = -1;
    int nxtEnd = -1;
    vector<int> shift = { 1, 12, 21, 28, 34 };
    for (int i = 0; i < 4; i++) {
        int idx = shift[i];
        while (cur < end) {
            if (cur <= n && n < cur+gaps[i]) {
                bit_set(idx);
                nxt = cur;
                nxtEnd = cur + gaps[i];
            }
            cur += gaps[i];
            idx++;
        }
        cur = nxt;
        end = nxtEnd;
    }
}

int compare(int b) {
    vector<int> gaps = { 373, 42, 6, 1 };
    // vector<int> shift = { 11, 9, 7, 6 };
    vector<int> shift = { 1, 12, 21, 28, 34 };
    int cur = 0;
    for (int i = 0; i < 4; i++) {
        int idx = shift[i];
        while (true) {
            if (cur <= b && b < cur + gaps[i]) {
                break;
            }
            cur += gaps[i];
            idx++;
        }
        if (!bit_get(idx)) {
            int lowerIndex = shift[i], upperIndex = shift[i+1]-1;
            if (idx - lowerIndex < upperIndex - idx) {
                // ask [lowerIndex...index)
                while (lowerIndex < idx) {
                    if (bit_get(lowerIndex)) return 1;
                    lowerIndex++;
                }
                return -1;
            } else {
                // ask (index...upperIndex]
                idx++;
                while (idx <= upperIndex) {
                    if (bit_get(idx)) return -1;
                    idx++;
                }
                return 1;
            }
        }
    }
    return 0;
}

• Subtask 1: 100 / 100