Submission #256329

#	Time	Username	Problem	Language	Result	Execution time	Memory
256329		tincamatei	Jousting tournament (IOI12_tournament)	C++14	0 / 100	26 ms	4276 KiB

tournament

#include <cstdio>
#include <cstdlib>

const int MAX_N = 100000;
const int MAX_C = 100000;

struct Node {
  bool active;
  int left, right, dep, bestpos;
} list[1+MAX_N];

int sp[1+MAX_N];

int getkth(int K) {
  int first = -1;
  for(int i = 0; i <= K; ++i) {
    ++first;
    while(!list[first].active)
      ++first;
  }
  return first;
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
  int respos = 0, resdep = 0;
  for(int i = 0; i < N; ++i)
    list[i] = {true, i, i, 0, i};
  
  sp[0] = (K[0] < R);
  for(int i = 1; i < N; ++i)
    sp[i] = sp[i - 1] + (K[i] < R);
  
  for(int i = 0; i < C; ++i) {
    Node resnode = {true, MAX_N + 1, -1, -1, -1};
    for(int t = 0; t < E[i] - S[i] + 1; ++t) {
      int nod = getkth(S[i]);
      
      if(list[nod].left < resnode.left)
        resnode.left = list[nod].left;
      if(list[nod].right > resnode.right)
        resnode.right = list[nod].right;
      if(list[nod].dep + 1 > resnode.dep) {
        resnode.dep = list[nod].dep + 1;
        resnode.bestpos = list[nod].bestpos;
      }
    
      list[nod].active = false;
    }

    list[E[i]] = resnode;
  
    int sum = 0;
    if(resnode.right - 1 >= 0)
      sum += sp[resnode.right - 1];
    if(resnode.left - 1 >= 0)
      sum -= sp[resnode.left - 1];
    if(sum == resnode.right - resnode.left && resnode.dep > resdep) {
      resdep = resnode.dep;
      respos = resnode.bestpos;
    }
  }
  
  return respos;
}

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