提出 #48686403

---

ソースコード 拡げる

#include <vector>
#include <cassert>
#include <iostream>
#include <utility>

struct Event{
    int event_type;
    int x;
};

int main(){
    int N; std::cin >> N;
    // {(t_i, x_i)}_i
    std::vector<Event> events(N);
    for (int i = 0; i < N; i ++) {
        int t, x; std::cin >> t >> x;
        x--;
        events[i] = {t, x};
    }

    // [i]: 時刻tにおいて、.back()は最後にあったタイプiのポーションの位置を示す。
    // すでに使用したポーションは省かれる。(スタック)
    std::vector<std::vector<int>> position_portion(N);
    // [i]がtrue: 位置iのポーションを取る
    std::vector<bool> getting_portion(N, false);
    for (int t = 0; t < N; t++) {
        const auto [event_type, x] = events[t];
        switch (event_type) {
            case 1:
                position_portion[x].push_back(t);
                break;
            case 2:
                // 取れるポーションが一切なかった場合ゲームオーバー
                if (position_portion[x].empty()){
                    std::cout << -1 << std::endl;
                    return 0;
                }
                // 現地点tから一番近い箇所にいるポーションxの位置
                const int portion_x_nearest = position_portion[x].back();
                position_portion[x].pop_back();
                getting_portion[portion_x_nearest] = true;
                break;
        }
    }
    
    // 値K
    int max_portion_count = 0;
    {
        // 時刻tにおいて持っているポーションの数
        int count_portion = 0;
        for (int t = 0; t < N; t++) {
            if (getting_portion[t]) { count_portion++; }
            if (events[t].event_type == 2) {
                assert(not getting_portion[t]);
                count_portion--;
            }
            max_portion_count = std::max(max_portion_count, count_portion);
        }
    }
    
    std::cout << max_portion_count << std::endl;
    for (int i = 0; i < N; i++) {
        if (events[i].event_type == 1) {
            std::cout << (getting_portion[i] ? 1 : 0);
            if (i != N - 1) { std::cout << " "; }
        }   
    }
    std::cout << std::endl;
    return 0;
}

// メモ
// 命名規則
    // portionに関する何らかの変数が多く宣言されているので
    // portionの何であるかという内容を先に持ってくる命名規則をとった

提出情報

ジャッジ結果