Submission #532613

#	Time	Username	Problem	Language	Result	Execution time	Memory
532613		cig32	Jousting tournament (IOI12_tournament)	C++17	49 / 100	1080 ms	4456 KiB

tournament

#include "bits/stdc++.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
using namespace std;
const int MOD = 1e9 + 7;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
#define inbuf_len 1 << 16
#define outbuf_len 1 << 16

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E);

#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 dsu[N];
  for(int i=0; i<N; i++) dsu[i] = i;
  for(int i=0; i<C; i++) {
    int lb = 0, rb = N - 1;
    while(lb < rb) {
      int mid = (lb + rb) >> 1;
      if(dsu[mid] >= S[i]) rb = mid;
      else lb = mid + 1;
    }
    int lb2 = 0, rb2 = N - 1;
    while(lb2 < rb2) {
      int mid = (lb2 + rb2 + 1) >> 1;
      if(dsu[mid] <= E[i]) lb2 = mid;
      else rb2 = mid - 1;
    }
    for(int j=lb + 1; j<=lb2; j++) dsu[j] = dsu[lb];
    for(int j=lb2 + 1; j<N; j++) dsu[j] -= (E[i] - S[i]);
    S[i] = lb, E[i] = lb2;
  }
  /*
  for(int i=0; i<C; i++) {
    cout << "Range #" << i <<": " << S[i] << " " << E[i] << "\n";
  }
  */
  int opt_cnt = 0, opt_id = 0;
  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: 17 / 17
• Subtask 2: 32 / 32
• Subtask 3: 0 / 51