oj.uz

답안 #1034373

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1034373 2024-07-25T12:51:19 Z vjudge1 비교 (balkan11_cmp) C++17
0 / 100
 466 ms 105160 KB 
#include "cmp.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> idx[12];

void remember(int a) {
  int curr = 1;
  for (int i = 0; i < 12; i++) {
    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 curr = 1;
  for (int i = 0; i < 12; i++) {
    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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 466 ms 105160 KB ZERO POINTS: For a=479 and b=1004, correct answer is 1, got -1