#330170 (C++14) No.190 Dry Wet Moist

• 問題: No.190 Dry Wet Moist
• ユーザー: commy
• 提出日時: 2019-03-30 01:21:29
• 言語: C++14 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 97 ms / 2,000 ms
• コード長: 1,976 bytes
• コンパイル時間: 995 ms
• コンパイル使用メモリ: 89,544 KB
• 実行使用メモリ: 13,296 KB
• 最終ジャッジ日時: 2024-11-07 01:37:39
• 合計ジャッジ時間: 4,018 ms
• ジャッジサーバーID （参考情報）: judge5 / judge1

ファイルパターン	結果
sample	AC * 2
other	AC * 28

ソースコード

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
#ifdef _DEBUG_
#define dump(val) cerr << __LINE__ << ":\t" << #val << " = " << (val) << endl
#else
#define dump(val)
#endif
using namespace std;
typedef long long int ll;
template<typename T>
vector<T> make_v(size_t a, T b) {
    return vector<T>(a, b);
}
template<typename... Ts>
auto make_v(size_t a, Ts... ts) {
    return vector<decltype(make_v(ts...))>(a, make_v(ts...));
}
int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> a, b;
    int zero = 0;
    REP(i, 0, 2 * n) {
        int v;
        cin >> v;
        if (v < 0) {
            a.push_back(-v);
        } else if (v > 0) {
            b.push_back(v);
        } else {
            zero++;
        }
    }
    sort(rbegin(a), rend(a));
    sort(rbegin(b), rend(b));
    auto Wet = [&]() -> int {
        int ans = 0;
        int j = 0;
        REP(i, 0, b.size()) {
            while (j < a.size() && b[i] <= a[j]) {
                j++;
            }
            if (j >= a.size()) {
                int rest = b.size() - i;
                int m = min(rest, zero);
                ans += m;
                rest -= m;
                ans += rest / 2;
                break;
            }
            ans++;
            j++;
        }
        return ans;
    };
    auto Dry = [&]() -> int {
        swap(a, b);
        int res = Wet();
        swap(a, b);
        return res;
    };
    auto Moist = [&]() -> int {
        int res = zero / 2;
        map<int, int> ma, mb;
        REP (i, 0, a.size()) {
            ma[a[i]]++;
        }
        REP (i, 0, b.size()) {
            mb[b[i]]++;
        }
        for (auto &it : ma) {
            res += min(it.second, mb[it.first]);
        }
        return res;
    };
    cout << Dry() << " " << Wet() << " " << Moist() << endl;
    return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX