Submission #513524

#	Time	Username	Problem	Language	Result	Execution time	Memory
513524		600Mihnea	Jousting tournament (IOI12_tournament)	C++17	100 / 100	159 ms	12876 KiB

tournament

#include <bits/stdc++.h>

using namespace std;

const int N = (int) 1e5 + 7;

int aib[N], my_n;

void clr() {
  for (int i = 1; i <= my_n; i++) {
    aib[i] = 0;
  }
}

void add(int i, int x) {
  while (i <= my_n) {
    aib[i] += x;
    i += i & (-i);
  }
}

int get(int i) {
  int sol = 0;
  while (i) {
    sol += aib[i];
    i -= i & (-i);
  }
  return sol;
}

int fnd(int k) {
  int init_k = k;
  int pos = 0, step = (1 << 20);
  while (step) {
    if (pos + step <= my_n && aib[pos + step] < k) {
      pos += step;
      k -= aib[pos];
    }
    step /= 2;
  }
  return pos + 1;
}

int a[N], init_ranks[N], st[N], dr[N], nxtbase[N];


int get(int i, int p) {
  if (i < p) {
    return nxtbase[i] + (nxtbase[i] >= p);
  }
  if (i == p) {
    return nxtbase[i] + 1;
  }
  if (i > p) {
    return nxtbase[i - 1] + 1;
  }
}

vector<int> in[N], out[N];

int GetBestPosition(int n, int cnt, int my_rank, int *_init_ranks, int *_st, int *_dr) {
  /// example -> solution = 1
  my_n = n;
  clr();
  for (int i = 1; i <= n; i++) {
    add(i, 1);
  }
  for (int i = cnt; i >= 1; i--) {
    st[i] = _st[i - 1] + 1;
    dr[i] = _dr[i - 1] + 1;
  }
  my_rank++;
  for (int i = n - 1; i >= 1; i--) {
    init_ranks[i] = _init_ranks[i - 1] + 1;
  }
  st[0] = dr[0] = init_ranks[0] = 0;
  int sz = n;
  for (int i = 1; i <= cnt; i++) {
    int X = st[i], Y = dr[i];
    if (dr[i] == sz) {
      dr[i] = n;
    } else {
      dr[i] = fnd(dr[i] + 1) - 1;
    }
    st[i] = fnd(st[i]);
    for (int j = Y; j > X; j--) {
      add(fnd(j), -1);
      sz--;
    }
  }
  for (int i = 1; i < n; i++) {
    if (init_ranks[i] < my_rank) {
      init_ranks[i] = 0;
    } else {
      init_ranks[i] = 2;
    }
  }
  int best = -1, sol = -1;
  bool debug = 1;
  nxtbase[n] = n;
  for (int i = n - 1; i >= 1; i--) {
    if (init_ranks[i] == 2) {
      nxtbase[i] = i;
    } else {
      nxtbase[i] = nxtbase[i + 1];
    }
  }
  for (int i = 1; i <= cnt; i++) {
    in[st[i]].push_back(i);
    out[dr[i] + 1].push_back(i);
  }
  clr();
  sz = 0;
  for (int p = 1; p <= n; p++) {
    for (auto &i : in[p]) {
      add(i, +1);
      sz++;
    }
    for (auto &i : out[p]) {
      add(i, -1);
      sz--;
    }
    int cur = 0;
    int low = 1, high = sz;
    while (low <= high) {
      int mid = (low + high) / 2;
      int i = fnd(mid);
      if (get(st[i], p) > dr[i]) {
        cur = mid;
        low = mid + 1;
      }  else {
        high = mid - 1;
      }
    }
    if (cur > best) {
      best = cur;
      sol = p;
    }
  }
  return sol - 1;
}

Compilation message (stderr)

tournament.cpp: In function 'int fnd(int)':
tournament.cpp:32:7: warning: unused variable 'init_k' [-Wunused-variable]
   32 |   int init_k = k;
      |       ^~~~~~
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:99:8: warning: unused variable 'debug' [-Wunused-variable]
   99 |   bool debug = 1;
      |        ^~~~~
tournament.cpp: In function 'int get(int, int)':
tournament.cpp:57:1: warning: control reaches end of non-void function [-Wreturn-type]
   57 | }
      | ^

• Subtask 1: 17 / 17
• Subtask 2: 32 / 32
• Subtask 3: 51 / 51