Submission #1237844

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237844		guanex	Jousting tournament (IOI12_tournament)	C++20	49 / 100	1093 ms	3516 KiB

tournament

#include<bits/stdc++.h>

using namespace std;

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
  vector<int> pref(N+1);
  vector<int> suff(N+1);
  vector<int> knights;
  int defeat = 0;
  for(int i = 0; i < N-1; ++i){
    if(K[i] > R){
      defeat++;
      pref[i]++;
      suff[i]++;
    }
  }
  vector<pair<int, int>> x;
  for(int i = 0; i < N; ++i){
    pref[i+1] += pref[i];
    suff[N-i-1] += suff[N-i];
    x.push_back({i, i});
  }
  vector<int> sweep(N+1);
  for(int i = 0; i < C; ++i){
    int l = x[S[i]].first;
    int r = x[E[i]].second;
    x.erase(x.begin()+S[i], x.begin()+E[i]+1);
    x.insert(x.begin() + S[i], {l, r});
    if(l > 0){
      if(pref[l-1] + suff[r] >= defeat){
        sweep[l]++;
        sweep[r+1]--;
      }
    }else{
      if(suff[r] >= defeat){
        sweep[l]++;
        sweep[r+1]--; 
      }
    }
  }
  int ans = -1;
  int act = 0;
  int pos = 0;
  for(int i = 0; i <= N-1; ++i){
    act += sweep[i];
    if(act > ans){
      ans = act;
      pos = i;
    }
  }
  return pos;
}

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