Submission #513465

#	Time	Username	Problem	Language	Result	Execution time	Memory
513465		600Mihnea	Jousting tournament (IOI12_tournament)	C++17	0 / 100	1065 ms	1860 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;
  }
  assert(get(pos + 1) == init_k);
  return pos + 1;
}

int a[N], nxt2[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 {
      assert(init_ranks[i] > my_rank);
      init_ranks[i] = 2;
    }
  }
  int best = -1, sol = -1;

  for (int p = 1; p <= n; p++) {
    int cur = 0;
    for (int i = 1; i < p; i++) {
      a[i] = init_ranks[i];
    }
    a[p] = 1;
    for (int i = p + 1; i <= n; i++) {
      a[i] = init_ranks[i - 1];
    }
    nxt2[n + 1] = n + 1;
    for (int i = n; i >= 1; i--) {
      if (a[i] == 2) {
        nxt2[i] = i;
      } else {
        nxt2[i] = nxt2[i + 1];
      }
    }
    for (int i = 1; i <= cnt; i++) {
      if (nxt2[st[i]] <= dr[i]) {
        break;
      }
      cur += (st[i] <= p && p <= dr[i]);
    }
    if (cur > best) {
      best = cur;
      sol = p;
    }
  }
  assert(sol != -1);
  return sol - 1;
}

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