oj.uz

답안 #1034398

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1034398 2024-07-25T13:18:24 Z vjudge1 비교 (balkan11_cmp) C++17
46 / 100
 2847 ms 105040 KB 
#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 >> (11-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 >> (11-i)) & 1) b ^= (1 << i);
  }

  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
46.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 2847 ms 105040 KB Output is partially correct - maxAccess = 16, score = 46