제출 #1149666

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1149666		hgmhc	비교 (balkan11_cmp)	C++17	100 / 100	916 ms	83224 KiB

cmp

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

struct node {
    int l, r, offset;
} t[20]{};

int substr(int n, int l, int r) {
    n &= (1<<r) - 1;
    n >>= l;
    return n;
}

// 875 = 0011 0110 1011

void remember(int n)
{
    t[1].l = 4;
    t[1].r = 12;
    
    t[2].l = 8;
    t[2].r = 12;
    
    t[3].l = 0;
    t[3].r = 4;
    
    t[4].l = 10;
    t[4].r = 12;
    
    t[5].l = 6;
    t[5].r = 8;
    
    t[6].l = 2;
    t[6].r = 4;
    
    int s = 1;
    
    for (int idx : {1, 2, 3, 4, 5, 6}) {
        auto &[l,r,o] = t[idx];
        
        o = s;
        
        bit_set(o + substr(n, l, r));
        
        s += 1<<(t[idx].r-t[idx].l);
    }
}

int compare(int b)
{
    int idx = 1;
    
    while (true)
    {
        if (idx == 4 || idx == 5 || idx == 6) break;
        auto [l,r,o] = t[idx];
        
        if (!bit_get(o + substr(b, l, r))) {
            idx = 2 * idx;
        }
        else {
            if (idx == 3) {
                return 0;
            }
            idx = 2 * idx + 1;
        }
    }
    
    if (idx == 4 || idx == 5 || idx == 6) {
        int jdx = idx/2;
        if (idx == 5) jdx = 1;
        
        if (bit_get(t[idx].offset + substr(b, t[idx].l, t[idx].r))) {
            
            int x = b>>t[jdx].l&1;
            int y = b>>(t[jdx].l+1)&1;
            
            if (x==y) {
                if (x) return +1;
                return -1;
            }
            else {
                if (x) { // 01
                    if (bit_get(t[jdx].offset + (substr(b,t[jdx].l,t[jdx].r) &~3))) return +1;
                    return -1;
                }
                else { // 10
                    if (bit_get(t[jdx].offset + (substr(b,t[jdx].l,t[jdx].r) | 3) )) return -1;
                    return +1;
                }
            }
        }
    }
    
    int x = b>>t[idx].l&1;
    int y = b>>(t[idx].l+1)&1;
    
    // b<a:-1
    if (x==y) {
        if (x) return +1;
        return -1;
    }
    else {
        if (x) { // 01 <-- 얘 있는 경우 --> 00이 존재한다면 b가 크다는 뜻
            if (bit_get(t[idx].offset)) return +1;
            return -1;
        }
        else { // 10 <-- 얘 있는 경우 --> 11이 존재한다면 b가 작다는 뜻
            if (bit_get(t[idx].offset + 3)) return -1;
            return +1;
        }
    }
}

• Subtask 1: 100 / 100