제출 #1034382

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1034382		vjudge1	비교 (balkan11_cmp)	C++17	0 / 100	450 ms	105092 KiB

cmp

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

vector<int> idx[12];

void remember(int a) {
  int A = a;
  
  a = 0;
  for (int i = 0; i < 12; i++) {
    if (!((A >> i) & 1)) a ^= (1 << i);
  }

  int curr = 1;
  for (int i = 0; i < 12; i++) {
    idx[i].clear();
    idx[i].resize(1 << (i+1));
    
    for (int j = 0; j < (1 << (i+1)); j++) {
      idx[i][j] = curr++;
    }
  }

  int sum = 0;
  for (int i = 0; i < 12; i++) {
    if ((a >> i) & 1) sum += (1 << i);  
    bit_set(idx[i][sum]);
  }
}

int compare(int b) {
  int B = b;
  
  b = 0;
  for (int i = 0; i < 12; i++) {
    if (!((B >> i) & 1)) b ^= (1 << i);
  }

  int curr = 1;
  for (int i = 0; i < 12; i++) {
    idx[i].clear();
    idx[i].resize(1 << (i+1));
    
    for (int j = 0; j < (1 << (i+1)); j++) {
      idx[i][j] = curr++;
    }
  }

  int sum[12];
  for (int i = 0; i < 12; i++) {
    sum[i] = (i ? sum[i-1] : 0) + (((b >> i) & 1) ? (1 << i) : 0);
  }
  
  int l = 0;
  int r = 12;
  while (l < r) {
    int mid = (l+r) >> 1;

    // difieren en el bit mid?
    // el prefix hasta i es igual?
    if (bit_get(idx[mid][sum[mid]])) l = mid+1;
    else r = mid;
  }

  if (l == 12) return 0;
  else if ((b >> l) & 1) return -1;
  else return 1;
}

• Subtask 1: 0 / 100