Submission #796468

#	Time	Username	Problem	Language	Result	Execution time	Memory
796468		esomer	마상시합 토너먼트 (IOI12_tournament)	C++17	0 / 100	1072 ms	3668 KiB

tournament

#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;

//~ }

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