結果

問題 No.507 ゲーム大会(チーム決め)
ユーザー Guowen Rong
提出日時 2025-02-24 17:47:14
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 483 ms / 3,000 ms
コード長 1,641 bytes
コンパイル時間 1,617 ms
コンパイル使用メモリ 167,312 KB
実行使用メモリ 8,576 KB
最終ジャッジ日時 2025-02-24 17:47:22
合計ジャッジ時間 7,017 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

 #include<bits/stdc++.h>
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define fi first
#define se second
#define open(s1, s2) freopen(s1, "r", stdin), freopen(s2, "w", stdout);
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const int N = 1e5 + 10;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
	if(x < 0){
		putchar('-');
		x = -x;
	}
	if(x > 9)
	  write(x / 10);
	putchar(x % 10 + '0');
}
int n, k, l, r, ans;
int a[N];
multiset<int> S;
inline bool check(int x){
	S.clear(); 
	int me = a[1] + a[x], sum = 0;
	for(int i = n; i >= 2; --i){
		if(i == x)
		  continue;
		S.insert(a[i]);
	}
	for(int i = n; i >= 2; --i){
		if(!S.count(a[i]) || i == x)
		  continue;
		int t = me - a[i] + 1;
		auto it = S.lower_bound(t);
		if(it != S.end() && ((*it) != a[i] || S.count(a[i]) > 1)){
			++sum;
			S.erase(it);
			S.erase(S.find(a[i]));
		}
	}
	return (sum < k);
}
bool End;
int main(){
//	open("prize.in", "prize.out");
	n = read(), k = read();
	for(int i = 1; i <= n; ++i)
	  a[i] = read();
	sort(a + 2, a + n + 1);
	l = 2, r = n;
	while(l <= r){
		int mid = (l + r) >> 1;
		if(check(mid)){
			ans = mid;
			r = mid - 1;
		}
		else
		  l = mid + 1;
	}
	if(!ans){
		puts("-1");
		exit(0);
	}
	write(a[ans]);
	cerr << '\n' << abs(&Begin - &End) / 1048576 << "MB";
	return 0;
}
0