Algoogle

Algorithm for Programming Contest

JOI 春合宿 2011 IOI

Category: JOI Tag: binary-search

IOI

問題概要


K人のコンテスタントがいて, 総問題数NのうちM個が終わった時の得点が与えられる.
全体の1/12人以上になるような点数のボーダーのうち, 最大の得点を金メダルのボーダーとする.
このとき金メダルが確定している選手と, 金メダルの可能性がある選手を求めよ

解法


金メダル確実な場合というのは自分が今後0点かつ他人がそれ以降全員満点をとっても自分より点数が大きい人がK/12人未満ということ.
これは現在の得点でソートされた列に対して自分の得点-残り全て満点の点数でupper_boundをとればよい.
ただし残りが0問の場合以外は自分もそこに含まれてしまうので除いておくこと.

金メダルの可能性があるというのは自分が今後満点かつ他人がそれ以降全員0点のとき自分より点数が大きい人がK/12人未満ということ.
これは同じように自分の得点+残り全て満点の点数でupper_boundをとればよい.
これには自分含まれることはない

コード


(ioi.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;

int k, n, m, p[1<<17], q[1<<17], res;

void solve()
{
        sort(q, q+k);
        res = 100*(n-m);
        for (int i = 0; i < k; i++) {
                int up = q+k-upper_bound(q,q+k, p[i]-res)-(res>0);
                if(12*up < k) cout << i+1 << endl;
        }
        cout << "--------" << endl;
        for (int i = 0; i < k; i++) {
                int up = q+k-upper_bound(q,q+k,p[i]+res);
                if(12*up < k) cout << i+1 << endl;
        }
}

void input()
{
        cin >> k >> n >> m;
        for (int i = 0; i < k; i++) cin >> p[i], q[i] = p[i];
}

int main()
{
        cin.tie(0);
        cin.sync_with_stdio(0);
        input();
        solve();
        return 0;
}

Comments