WARush

SRMの結果とか、解けた問題のコードを書いていきます

Codeforces #187 Div2 C "Sereja and Contest"

問題

http://codeforces.com/contest/315/problem/C

この前のセレジャの"Codesecrof"のプログラミングコンテストは、長時間サーバーがクラッシュしたので何人かの参加者をunratedにすることを決定した。

コンテストの参加人数をnとする。そして、最初の参加者のレーティングをa_1、2番目の参加者のレーティングをa2, ... n番目の参加者のレーティングをa_nとしよう。それから"Codesecrof"では以下のような式を計算してレーティングが変更する。
TODO

ラウンドが完了した後、Codesecrof運営者は参加者の成績(結果テーブル)を公開する。彼はd_i < kである参加者は、当該ラウンドにおいて、uprateにすることに決めていた。しかし、結果テーブルは動的であることが判明したときは、運営者は驚いた事だろう。言い換えれば、ある参加者が除外(unrate)になると、結果テーブルからも彼の情報が除外され、新しい結果テーブルを元にして、再度レーティング変更の計算が行われる。そしてもちろん、レーティング変更のためのアプリケーションは最新のテーブルを参照する。

- 略 -

何番目の参加者が除外されるのか出力せよ

制約

1 <= n <= 2 * 10^5
-10^9 <= k <= 0



考えた事

問題を推理して、正確に実装できるかと言う問題。
計算量を多く見積もらせようとしてるのか、問題文が・・・

訳すの諦めた

事後

intでオーバーフロー
もーなんなんだよ!!



ソースコード

int n, k; // 参加者数, k
int e; // 除外者数
long long sum; // 残っている人のポイント


int main() {

    e = 0;
    sum = 0;

    cin >> n >> k;

    for( int i = 1; i <= n; i++ ){
        long long rate;
        cin >> rate;

        if( i == 1 ) continue;

        long long dif = rate * ( n - i ) * ( i - 1 - e );
        long long d = sum - dif;
        if( d < k ){
            e++; // 除外!
            printf( "%d ", i );
        }else{
            sum += (i - e - 1) * rate;
        }
    }
}