Submission #532594

#	Time	Username	Problem	Language	Result	Execution time	Memory
532594		cig32	Jousting tournament (IOI12_tournament)	C++17	0 / 100	1076 ms	4964 KiB

tournament

#include "bits/stdc++.h"
using namespace std;

const int MAXN = 1e5 + 10;
int st[17][MAXN];
int query(int l, int r) {
  int k = 32 - __builtin_clz(r-l+1) - 1; return max(st[k][l], st[k][r - (1<<k) + 1]);
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
  int og[C];
  for(int i=0; i<C; i++) og[i] = E[i] - S[i];
  for(int i=0; i<C; i++) {
    for(int j=i+1; j<C; j++) {
      if(S[j] > S[i]) S[j] += og[i];
      if(E[j] >= S[i]) E[j] += og[i];
    }
  }
  int opt_cnt = 0, opt_id = -1;
  for(int P=0; P<N; P++) {
    vector<int> now;
    for(int j=0; j<P; j++) now.push_back(K[j]);
    now.push_back(R);
    for(int j=P; j<N; j++) now.push_back(K[j]);
    for(int j=0; j<N; j++) st[0][j] = now[j];
    for(int j=1; j<17; j++) {
      for(int k=0; k<N; k++) {
        if(k + (1<<j) - 1 < N) {
          st[j][k] = max(st[j-1][k], st[j-1][k + (1 << (j-1))]);
        }
      }
    }
    int ok = 0;
    for(int j=0; j<C; j++) {
      ok += (query(S[j], E[j]) == R);
    }
    if(ok > opt_cnt) {
      opt_cnt = ok;
      opt_id = P;
    }
  }
  return opt_id;
}

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