Submission #660874

#	Time	Username	Problem	Language	Result	Execution time	Memory
660874		600Mihnea	cmp (balkan11_cmp)	C++17	100 / 100	2554 ms	94988 KiB

cmp

#include "cmp.h"

#include <bits/stdc++.h>

using namespace std;

vector<int> cnt = {12, 10, 8, 6};

bool first = 1;
int P[100000];
int W[100000];
int L, R;

void remember(int n)
{
  bool debug = (n == 2671);
  if (first)
  {
    L = 1, R = 1;
    for (int level = 0; level < (int) cnt.size(); level++)
    {
      int branch = cnt[level];
      int CNT = R - L + 1;
      int Lant = L, Rant;
      L = R + 1;
      R = R + CNT * branch;
      for (int j = L; j <= R; j++)
      {
        P[j] = Lant + (j - L) / branch;
        W[j] = (j - L) % branch;
      }
    }
    first = 0;
  }
  n = L + n;
  for (int level = (int) cnt.size() - 1; level >= 0; level--)
  {
    bit_set(n);
    n = P[n];
  }
}


int c = 0;

int compare(int n)
{
  c++;
  if (c % 100000 == 0)
  {
   /// cout << " d " << c << "\n";
  }
  vector<int> path;
  bool debug = (n == 2671);
  n = L + n;
  for (int level = (int) cnt.size() - 1; level >= 0; level--)
  {
    path.push_back(n);
    n = P[n];
  }
  reverse(path.begin(), path.end());
  for (int level = 0; level < (int) cnt.size(); level++)
  {
    if (bit_get(path[level]) == 0)
    {
      int Start = path[level] - W[path[level]];
      int End = Start + cnt[level] - 1;
      if (path[level] - Start < End - path[level])
      {
        for (int j = Start; j < path[level]; j++)
        {
          if (bit_get(j))
          {
            return +1;
          }
        }
        return -1;
      }
      else
      {
        for (int j = path[level] + 1; j <= End; j++)
        {
          if (bit_get(j))
          {
            return -1;
          }
        }
        return +1;
      }
    }
  }
  return 0;
}

Compilation message (stderr)

cmp.cpp: In function 'void remember(int)':
cmp.cpp:24:21: warning: unused variable 'Rant' [-Wunused-variable]
   24 |       int Lant = L, Rant;
      |                     ^~~~
cmp.cpp:16:8: warning: unused variable 'debug' [-Wunused-variable]
   16 |   bool debug = (n == 2671);
      |        ^~~~~
cmp.cpp: In function 'int compare(int)':
cmp.cpp:54:8: warning: unused variable 'debug' [-Wunused-variable]
   54 |   bool debug = (n == 2671);
      |        ^~~~~

• Subtask 1: 100 / 100