Codeforces Round #208 (Div. 2) C. Dima and Containers

,

練習会で3人が挑んで2人が誤読した。誤読した。

C. Dima and Containers

問題

stack, queue 及び deque がひとつずつある。 以下のクエリが与えられる。取り出した数の総和を最大化せよ。

  1. 数$a_i \gt 0$が指定される。いずれかのcontainerにこれを追加する。
  2. それぞれのcontainerから要素をひとつずつ取り出す。既に空なら無視する。その後全てのcontainerを空にする。

解法

pushする数に関して、それをpopすることになるのかどうかを事前に判定しておく。

実装

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;
int main() {
    int n; cin >> n;
    vector<int> a(n); repeat (i,n) cin >> a[i];
    vector<bool> used(n); {
        priority_queue<pair<int,int> > q;
        repeat (i,n) {
            if (a[i] == 0) {
                for (int j = 0; j < 3 and not q.empty(); ++ j) {
                    int weight, index; tie(weight, index) = q.top(); q.pop();
                    used[index] = true;
                }
                q = decltype(q)();
            } else {
                q.push(make_pair(a[i], i));
            }
        }
    }
    int j = 0;
    repeat (i,n) {
        if (a[i] == 0) {
            cout << j;
            if (j >= 1) cout << ' ' << "popStack";
            if (j >= 2) cout << ' ' << "popQueue";
            if (j >= 3) cout << ' ' << "popFront";
            cout << endl;
            j = 0;
        } else {
            if (used[i]) {
                switch (j) {
                    case 0: cout << "pushStack" << endl; ++ j; break;
                    case 1: cout << "pushQueue" << endl; ++ j; break;
                    case 2: cout << "pushFront" << endl; ++ j; break;
                }
            } else {
                cout << "pushBack" << endl;
            }
        }
    }
    return 0;
}