oj.uz

답안 #828694

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
828694 2023-08-17T13:48:13 Z jlallas384 마상시합 토너먼트 (IOI12_tournament) C++17
17 / 100
 1000 ms 251900 KB 
#include <bits/stdc++.h>
using namespace std;
struct tree{
	tree *lc = nullptr, *rc = nullptr;
	int sum = 0, l, r;
	tree(int i, int j){
		l = i, r = j;
		if(l == r){
			sum = 1;
		}else{
			int m = (l + r) / 2;
			lc = new tree(l, m);
			rc = new tree(m + 1, r);
			sum = lc->sum + rc->sum;
		}
	}
	void upd(int i){
		if(l == r){
			sum = 0;
		}else{
			if(i <= lc->r) lc->upd(i);
			else rc->upd(i);
			sum = lc->sum + rc->sum;
		}
	}
	int kth(int i){
		if(l == r) return l;
		int ls = lc->sum;
		if(i > ls) return rc->kth(i - ls);
		else return lc->kth(i);
	}
};


int GetBestPosition(int n, int c, int r, int k[], int s[], int e[]){
	vector<int> a;
	for(int i = 0; i < n - 1; i++){
		a.push_back(k[i]);
	}
	int bst = -1, idx = -1;
	for(int i = 0; i <= n - 1; i++){
		tree *st = new tree(0, n);
		set<int> sts;
		for(int i = 0; i < n; i++){
			sts.insert(i);
		}
		int ths = 0;
		for(int j = 0; j < c; j++){
			int li = st->kth(s[j] + 1), ri = st->kth(e[j] + 1);
			vector<pair<int,int>> arr;
			auto it = sts.lower_bound(li);
			while(it != sts.end() && *it <= ri){
				if(*it == i) arr.emplace_back(r, *it);
				else arr.emplace_back(k[*it - (*it > i)], *it);
				it = next(it);
			}
			sort(arr.begin(), arr.end());
			if(arr.back().first == r) ths++;
			for(int l = 0; l < arr.size() - 1; l++){
				st->upd(arr[l].second);
				sts.erase(arr[l].second);
			}
		}
		if(ths > bst){
			bst = ths;
			idx = i;
		}
	}
	return idx;
}

Compilation message

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:59:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |    for(int l = 0; l < arr.size() - 1; l++){
      |                   ~~^~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 3 ms 1236 KB Output is correct
3 Correct 99 ms 22680 KB Output is correct
4 Correct 90 ms 23756 KB Output is correct
5 Correct 75 ms 23796 KB Output is correct
6 Correct 103 ms 23780 KB Output is correct
7 Correct 94 ms 23740 KB Output is correct
8 Correct 97 ms 23756 KB Output is correct
9 Correct 63 ms 23792 KB Output is correct
10 Correct 76 ms 23768 KB Output is correct

Subtask #2
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 430 ms 94308 KB Output is correct
2 Execution timed out 1070 ms 251900 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1070 ms 144176 KB Time limit exceeded
2 Halted 0 ms 0 KB -