結果

問題 No.2182 KODOKU Stone
コンテスト
ユーザー Nachia
提出日時 2023-01-06 22:57:44
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,259 bytes
コンパイル時間 4,118 ms
コンパイル使用メモリ 134,376 KB
最終ジャッジ日時 2025-02-10 00:16:25
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 11 WA * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 1 "Main.cpp"
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <atcoder/modint>
#line 2 "nachia\\set\\word-size-tree.hpp"

#line 5 "nachia\\set\\word-size-tree.hpp"

namespace nachia{

struct WordsizeTree{
    using Word = unsigned long long;
    static constexpr int W = 64;
    int N;
    std::vector<std::vector<Word>> A;
    static int highBit(Word x){
        if(x == 0) return 0;
        return W-1 - __builtin_clzll(x);
    }
    static int lowBit(Word x){
        if(x == 0) return W;
        return __builtin_ctzll(x);
    }
    WordsizeTree(unsigned int length){
        N = length;
        int n = length;
        do {
            std::vector<Word> a(n/W+1,0);
            A.emplace_back(std::move(a));
            n /= W;
        } while(n);
    }
    WordsizeTree(const std::string& binStr = ""){
        N = binStr.size();
        int n = N;
        {
            std::vector<Word> a(n/W+1);
            for(int i=0; i<n; i++) if(binStr[i] == '1'){
                a[i/W] |= (Word)1 << (i%W);
            }
            A.emplace_back(std::move(a));
            n /= W;
        }
        while(n){
            std::vector<Word> a(n/W+1,0);
            for(int i=0; i<=n; i++){
                if(A.back()[i]) a[i/W] |= (Word)1 << (i%W);
            }
            A.emplace_back(std::move(a));
            n /= W;
        }
    }
    void insert(int x){
        for(auto& a : A){
            a[x/W] |= (Word)1 << (x % W);
            x /= W;
        }
    }
    void erase(int x){
        for(auto& a : A){
        a[x/W] &= ~((Word)1 << (x % W));
        if(a[x/W]) return;
        x /= W;
        }
    }
    int count(int x) const {
        return (int)((A[0][x/W] >> (x%W)) & 1);
    }
    int noLessThan(int x) const {
        int d = 0, i = x;
        while(true){
            if(d >= (int)A.size()) return -1;
            if(i/W >= (int)A[d].size()) return -1;
            Word m = A[d][i/W] & ((~(Word)0) << (i%W));
            if(!m){ d++; i /= W; i++; }
            else{
                int to = lowBit(m);
                i = i/W*W + to;
                if(d == 0) break;
                i *= W;
                d--;
            }
        }
        return i;
    }
    int noGreaterThan(int x) const {
        int d = 0, i = x;
        while(true){
            if(i < 0) return -1;
            if(d >= (int)A.size()) return -1;
            Word m = A[d][i/W] & ~((~(Word)1) << (i%W));
            if(!m){ d++; i /= W; i--; }
            else{
                int to = highBit(m);
                i = i/W*W + to;
                if(d == 0) break;
                i *= W;
                i += W-1;
                d--;
            }
        }
        return i;
    }
};

} // namespace nachia
#line 8 "Main.cpp"
using namespace std;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
const i64 INF = 1001001001001001001;

using Modint = atcoder::static_modint<998244353>;


int main(){
    int N; cin >> N;
    vector<int> K(N); rep(i,N) cin >> K[i];
    reverse(K.begin(), K.end());
    vector<vector<int>> A(N);
    rep(i,N){
        int t; cin >> t;
        A[i].resize(t);
        rep(j,t) cin >> A[i][j];
        sort(A[i].rbegin(), A[i].rend());
    }
    int L = 0, R = 1000000000;
    vector<int> H(N);
    while(L+1 < R){
        int x = (L+R)/2;
        rep(i,N) H[i] = min<int>(A[i].size(), upper_bound(A[i].begin(), A[i].end(), x, greater<int>()) - A[i].begin()) + 1;
        sort(H.begin(), H.end());
        nachia::WordsizeTree Hset(string(N, '1'));
        auto Take = [&](int h) -> bool {
            int hp = lower_bound(H.begin(), H.end(), h) - H.begin();
            int pos = Hset.noLessThan(hp);
            if(pos == -1) return false;
            Hset.erase(pos);
            return true;
        };
        bool ok = true;
        for(int k : K){
            if(Take(k+1)){ ok = true; break; }
            if(!Take(k)){ ok = false; break; }
        }
        (ok ? L : R) = x;
    }
    cout << L << endl;
    return 0;
}



struct ios_do_not_sync{
    ios_do_not_sync(){
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    }
} ios_do_not_sync_instance;
0