第8回日本情報オリンピック 春合宿 2日目 問題3 「コンテスト」 (Contest)

難しかったけど解ける気がしたのでめっちゃがんばって無理やり解いた。

WAとRE大量発生しまくってとてもつらい思いをした。

生のソースはっつけます。

解法とか書く気力がおきない。

#include <bits/stdc++.h>

using namespace std;
const int INF = 1000000000;
int n,c;
int sum[3002];
int kazu[3004];
int takai,hikui;
int pon[6004];
priority_queue<int> aki,kata;
bool ch(int r,priority_queue<int> aki,priority_queue<int> kata){
	if(takai >= r)return false;
	if(hikui > n - r)return true;
	while(kata.size() > n - r -hikui)kata.pop(),aki.pop(),takai++;
	int kaisu = 2*r - (aki.size()-n+r);
	// for(int i = 0;i < kaisu;i++)kata.pop(),aki.pop(),takai++;
	for(int i = 0;i < r-1-takai;i++){
	//	if(aki.empty())return false;
		aki.pop();//←　原因はここ
	/*	if( aki.empty()){
			kata.pop();
			continue;
		}
		if(kata.empty()){
			aki.pop();
			continue;
		}*/
		if(aki.top() > kata.top()){
			aki.pop();
		}else{
			kata.pop();
		}
	}
	takai = r-1;
	int co = 0;
	while(aki.size())pon[co++] = aki.top(),aki.pop();
	while(kata.size()){
		int hi = kata.top(); kata.pop();
		for(int i = 0;i < co;i++){
			if(pon[i] + hi <= sum[c]){
				pon[i] = INF;
				hikui++;
				goto out;
			}
		}
		return false;
out:
		;
	}
	while(hikui < n - r){
		int aa=INF,bb=INF;
		for(int i = 0;i < co;i++){
			if(pon[i] != INF){
				aa = pon[i];
				pon[i] = INF;
				break;
			}
		}
		for(int i = co -1;i >= 0;i--){
			if(pon[i] != INF){
				bb = pon[i];
				pon[i] = INF;
				break;
			}
		}
		if(aa + bb > sum[c])return false;
		hikui++;
	}
	return true;
}


int main(){
	scanf("%d%d",&n,&c);
	for(int i = 0;i < n*2;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		if(b == 0){
			aki.push(a);
		}
		sum[b] += a;
		kazu[b]++;
	}
	int tt=0,hh=0;
	for(;kazu[c] < 2;kazu[c]++){
		sum[c] += aki.top(); aki.pop();
	}
	//cout << "The C is " << sum[c] << endl;
	for(int i = 1;i <= n;i++){
		if(i == c)continue;
		if(kazu[i] == 2){
			if(sum[i] > sum[c])tt++;
			else hh++;
		}
		if(kazu[i] == 1){
			kata.push(sum[i]);
		}
	}
	int lb = -1,ub = n+1;
	while(ub - lb > 1){
		int mid = (lb + ub) / 2;
		takai = tt,hikui = hh;
		if(ch(mid,aki,kata)) ub = mid;
		else lb = mid;
	}
	printf("%d\n",ub);
	return 0;
}