# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
796466 | esomer | Jousting tournament (IOI12_tournament) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#include "tournament.h"
using namespace std;
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){
set<pair<int, int>> left;
int ans = 0;
int mx = 0;
for(int pos = 0; pos < N; pos++){
left.clear();
left.insert({pos, R});
for(int i = 0; i < N - 1; i++){
if(i < pos) left.insert({i, K[i]});
else left.insert({i+1, K[i]});
}
int wins = 0;
for(int i = 0; i < C; i++){
int l = S[i];
int r = E[i];
//The left_endpoint is always correct, because I update it.
int total = 0;
int mx = 0;
bool seen = 0;
auto it = left.lower_bound({l, -1});
vector<pair<int, int>> eras;
while(total < (r - l + 1)){
total++;
pair<int, int> p = *it; it++; eras.push_back(p);
mx = max(mx, p.second);
if(p.second == R) seen = 1;
}
for(pair<int, int> p : eras) left.erase(p);
if(seen){
if(mx > R) break;
else wins++;
}
left.insert({l, mx});
}
if(wins > mx){
mx = wins;
ans = pos;
}
}
return ans;
}
//~ int main() {
//~ int tmp;
//~ int N, C, R;
//~ int *K, *S, *E;
//~ tmp = scanf("%d %d %d", &N, &C, &R);
//~ assert(tmp == 3);
//~ K = (int*) malloc((N-1) * sizeof(int));
//~ S = (int*) malloc(C * sizeof(int));
//~ E = (int*) malloc(C * sizeof(int));
//~ int i;
//~ for (i = 0; i < N-1; i++) {
//~ tmp = scanf("%d", &K[i]);
//~ assert(tmp == 1);
//~ }
//~ for (i = 0; i < C; i++) {
//~ tmp = scanf("%d %d", &S[i], &E[i]);
//~ assert(tmp == 2);
//~ }
//~ printf("%d\n", GetBestPosition(N, C, R, K, S, E));
//~ return 0;
//~ }