Submission #1034397

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1034397	2024-07-25T13:17:47 Z	vjudge1	cmp (balkan11_cmp)	C++17	0 / 100	10000 ms	105040 KB

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 >> (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 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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	10031 ms	105040 KB	Time limit exceeded