結果

問題 No.3167 [Cherry 7th Tune C] Cut in Queue
コンテスト
ユーザー mkawa2
提出日時 2025-05-30 23:38:34
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,967 bytes
コンパイル時間 3,783 ms
コンパイル使用メモリ 293,096 KB
実行使用メモリ 24,612 KB
最終ジャッジ日時 2025-05-30 23:38:51
合計ジャッジ時間 16,194 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 10 TLE * 1 -- * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

const int LIM = 750;

vector<vector<int>> aa;
vector<set<int>> ss;
int b;
int top = 0;

// check function: 分割を管理する
void check(int g) {
    if ((int)aa[g].size() < LIM) return;
    int m = LIM / 2;
    aa.insert(aa.begin() + g + 1, vector<int>());
    ss.insert(ss.begin() + g + 1, set<int>());

    for (int i = 0; i < m; ++i) {
        int a = aa[g].back(); aa[g].pop_back();
        ss[g].erase(a);
        aa[g + 1].push_back(a);
        ss[g + 1].insert(a);
    }
    reverse(aa[g + 1].begin(), aa[g + 1].end());
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    aa.emplace_back();
    ss.emplace_back();

    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        if ((int)aa.back().size() == LIM - 1) {
            aa.emplace_back();
            ss.emplace_back();
        }
        aa.back().push_back(a);
        ss.back().insert(a);
    }

    b = n + 1;

    int q;
    cin >> q;
    while (q--) {
        int t;
        cin >> t;

        if (t == 1) {
            int a;
            cin >> a;
            int g, i;

            if (a != 0) {
                g = 0;
                while (!ss[g].count(a)) ++g;
                auto it = find(aa[g].begin(), aa[g].end(), a);
                i = distance(aa[g].begin(), it);
            } else {
                g = (int)aa.size() - 1;
                i = (int)aa[g].size();
            }

            aa[g].insert(aa[g].begin() + i, b);
            ss[g].insert(b);
            ++b;
            check(g);
        }
        else if (t == 2) {
            ++top;
        }
        else if (t == 3) {
            int k;
            cin >> k;
            k = k - 1 + top;

            int g = 0;
            while ((int)aa[g].size() <= k) {
                k -= aa[g].size();
                ++g;
            }
            cout << aa[g][k] << '\n';
        }
    }

    return 0;
}
0