제출 #241119

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
241119		rqi	마상시합 토너먼트 (IOI12_tournament)	C++14	17 / 100	1092 ms	1776 KiB

tournament

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pi;
typedef vector<int> vi;

#define mp make_pair
#define f first
#define s second
#define sz(x) (int)x.size()
#define ins insert
#define lb lower_bound
#define pb push_back

template<class T> bool ckmax(T& a, const T& b) { 
    return a < b ? a = b, 1 : 0; } 

/**
 * Description: A set (not multiset!) with support for finding the $n$'th
 * element, and finding the index of an element. Change \texttt{null\_type} for map.
 * Time: O(\log N)
 * Source: KACTL
 * Verification: many
 */

#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, 
	rb_tree_tag, tree_order_statistics_node_update>; 
#define ook order_of_key
#define fbo find_by_order

void treeExample() {
	Tree<int> t, t2; t.insert(8);
	auto it = t.insert(10).f; assert(it == t.lb(9));
	assert(t.ook(10) == 1 && t.ook(11) == 2 && *t.fbo(0) == 8);
	t.join(t2); // assuming T < T2 or T > T2, merge t2 into t
}

/**
int atMost(Tree<pi>& T, int r) { 
	return T.ook({r,MOD}); }
int getSum(Tree<pi>& T, int l, int r) { 
	return atMost(T,r)-atMost(T,l-1); }
*/

pi topi[200005];
int par[200005][30];
int curind = 0;

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	pi ans = mp(-1, -N);
	for(int i = 0; i < N; i++){
		vi curranks;
		int ind = 0;
		for(int j = 0; j <= N-1; j++){
			if(j == i) curranks.pb(R);
			else curranks.pb(K[ind++]);
		}
		int curans = 0;
		for(int j = 0; j < C; j++){
			vi newranks;
			bool isin = 0;
			int maxval = -1;
			for(int i = 0; i < sz(curranks); i++){
				if(S[j] <= i && i <= E[j]){
					if(curranks[i] == R){
						isin = 1;
					}
					ckmax(maxval, curranks[i]);
					if(i == E[j]){
						newranks.pb(maxval);
					}
					continue;
				}
				newranks.pb(curranks[i]);
			}
			swap(curranks, newranks);
			if(isin == 1 && maxval != R){
				break;
			}
			if(isin == 1) curans++;
		}
		//cout << i << " " << curans << "\n";
		ckmax(ans, mp(curans, -i));
	}
	return -ans.s;
}

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