답안 #362304

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
362304 2021-02-02T15:28:28 Z cheongm 비교 (balkan11_cmp) C++14
91 / 100
2123 ms 92988 KB
#include "cmp.h"
/*
   가장쉬운방법 비트로 저장 ->  최악 12, 12번
   그러면 트리로 범위 지정 2^12승이니까 (2^1,2^2,2^3,2^4,2^6,2^12)자식 
   2^1 -> 저장 12개, get 12개
   2^2 -> 저장 6개 , get 6+2개
   2^3 -> 저장 4개 , get 4+4개 << 최적으로 보인다.
   2^4 -> 저장 3개 , get 4+8개
   ...
   */
  
void remember(int n) {
    int bit_3[4];
    for(int i=0; i<4;i++)
    {
        bit_3[i] = n&((1<<3)-1);//n%8
        n>>=3;
    }
    int idx = 0;
    for(int i=3; i>=0;i--)
    {
        idx = idx*8+bit_3[i]+1;//이거생각하는데 꽤오래걸림
        bit_set(idx);
    }
}

int compare(int b) {
    int bit_3[4];
    for(int i=0; i<4;i++)
    {
        bit_3[i] = b&((1<<3)-1);
        b>>=3;
    }
    int idx = 0;
    for(int i=3; i>=0;i--)
    {
        idx = idx*8+bit_3[i]+1;
        if(!bit_get(idx))
        {
            if(bit_3[i]<4)
            {
                for(int j=1;bit_3[i]-j>=0;j++)
                {
                    if(bit_get(idx-j))
                        return 1;
                }
                return -1;
            }
            else
            {
                for(int j=1;bit_3[i]+j<8;j++)
                {
                    if(bit_get(idx+j))
                        return -1;
                }
                return 1;
            }
        }
    }
    return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Partially correct 2123 ms 92988 KB Output is partially correct - maxAccess = 11, score = 91