結果

問題 No.2182 KODOKU Stone
ユーザー MasKoaTS
提出日時 2022-11-29 12:20:55
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 1,318 bytes
コンパイル時間 2,574 ms
コンパイル使用メモリ 212,384 KB
最終ジャッジ日時 2025-02-09 02:07:48
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
#define rep(i, l, n) for (int i = (l); i < (n); i++)
#define all(x) x.begin(), x.end()
#define last(x) x[x.size() - 1]
using namespace std;
template <class T>  using V = vector<T>;
bool check(int& N, V<int>&K, V<V<int> >&A, int m) {
    deque<int> P = {};  deque<int> Q = {};
    rep(i, 0, N) {
        int s = 0;
        for (int a : A[i]) {
            s += (a >= m);
        }
        if (s < A[i].size()) {
            P.push_back(s);
        }
        else {
            Q.push_back(s);
        }
    }
    sort(all(P));   sort(all(Q));
    rep(i, 1, N + 1) {
        int k = K[N - i];
        int p = P.empty() ? -1 : last(P);
        int q = Q.empty() ? -1 : last(Q);
        if (max(p, q) >= k) {
            return true;
        }
        else if (i < N and p == k - 1) {
            P.pop_back();
        }
        else if (q != -1) {
            Q.pop_front();
        }
        else {
            return false;
        }
    }
    return true;
}
int main(void) {
    int N;  cin >> N;
    V<int> K(N);
    rep(i, 0, N) {
        cin >> K[i];
    }
    V<int> T(N);
    V<V<int> > A(N, V<int>({}));
    V<int> st = {};
    rep(i, 0, N) {
        cin >> T[i];
        rep(j, 0, T[i]) {
            int a;  cin >> a;
            A[i].push_back(a);
            st.push_back(a);
        }
    }
    st.erase(unique(all(st)), st.end());
    sort(all(st));
    int ok = 0, ng = st.size();
    while (ng - ok > 1) {
        int t = (ok + ng) >> 1;
        if (check(N, K, A, st[t])) {
            ok = t;
        }
        else {
            ng = t;
        }
    }
    int ans = st[ok];
    cout << ans << endl;
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0