結果

問題 No.190 Dry Wet Moist
ユーザー tottoripaper
提出日時 2015-07-02 18:47:14
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 1,555 bytes
コンパイル時間 262 ms
コンパイル使用メモリ 39,808 KB
実行使用メモリ 10,624 KB
最終ジャッジ日時 2024-07-07 22:15:45
合計ジャッジ時間 4,228 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other WA * 20 TLE * 1 -- * 7
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:38:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   38 |     scanf("%d", &N);
      |     ~~~~~^~~~~~~~~~
main.cpp:43:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   43 |         scanf("%d", &a);
      |         ~~~~~^~~~~~~~~~

ソースコード

diff # 

#include <cstdio>
#include <vector>
#include <algorithm>

int c1[100001], c_1[100001], c0;
int _c1[100001], _c_1[100001];

int count(int c1[100001], int c_1[100001], int c0){
    int res = 0;

    for(int i=100000,j=100000;i>0;i--){
        if(c1[i] == 0){continue;}

        if(j >= 0){
            while(j > 0 && (j >= i || c_1[j] == 0)){j -= 1;}
            if(j == 0){
                res += std::min(c1[i], c0);
                c0 -= std::min(c1[i], c0);
                if(c0 == 0){j = -1;}
            }else{
                res += std::min(c1[i], c_1[j]);
                c_1[j] -= std::min(c1[i], c_1[j]);
            }
        }else{
            while(-j < i && c1[-j] == 0){j += 1;}
            if(-j == i){break;}
            res += std::min(c1[i], c1[-j]);
            c1[-j] -= std::min(c1[i], c1[-j]);
        }
    }

    return res;
}
                                                   

int main(){
    int N;
    scanf("%d", &N);

    c0 = 0;
    for(int i=0;i<2*N;i++){
        int a;
        scanf("%d", &a);

        if(a > 0){
            c1[a] += 1;
        }else if(a == 0){
            c0 += 1;
        }else{
            c_1[-a] += 1;
        }
    }

    int dry, wet, moist = c0 / 2;
    for(int i=1;i<=100000;i++){
        moist += std::min(c1[i], c_1[i]);
    }

    std::copy(c1, c1+100001, _c1);
    std::copy(c_1, c_1+100001, _c_1);
    dry = count(_c_1, _c1, c0);

    std::copy(c1, c1+100001, _c1);
    std::copy(c_1, c_1+100001, _c_1);
    wet = count(_c1, _c_1, c0);    

    printf("%d %d %d\n", dry, wet, moist);
}
0