제출 #796468

#제출 시각아이디문제언어결과실행 시간메모리
796468esomer마상시합 토너먼트 (IOI12_tournament)C++17
0 / 100
1072 ms3668 KiB
#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; //~ }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...