답안 #412908

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
412908 2021-05-27T19:03:33 Z thecodingwizard 비교 (balkan11_cmp) C++11
100 / 100
2573 ms 82496 KB
#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;
}

# 결과 실행 시간 메모리 Grader output
1 Correct 2573 ms 82496 KB Output is correct - maxAccess = 10, score = 100