QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#390859#7108. CouleurKKT89RE 0ms0kbC++173.9kb2024-04-15 23:55:062024-04-15 23:55:07

Judging History

你现在查看的是最新测评结果

  • [2024-04-15 23:55:07]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-04-15 23:55:06]
  • 提交

answer

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) { return (ull)rng() % B; }

// 0-indexed
template <typename T> struct BIT {
    int n;
    vector<T> bit, ary;
    BIT(int n = 0) : n(n), bit(n + 1), ary(n) {}
    T operator[](int k) { return ary[k]; }
    // [0, i)
    T sum(int i) {
        T res = 0;
        for (; i > 0; i -= (i & -i)) {
            res += bit[i];
        }
        return res;
    }
    // [l, r)
    T sum(int l, int r) { return sum(r) - sum(l); }
    void add(int i, T a) {
        ary[i] += a;
        i++;
        for (; i <= n; i += (i & -i)) {
            bit[i] += a;
        }
    }
};

void slv() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    vector<BIT<int>> bit_memo(n);
    // [l, r) の転倒数と左端を始点としたBITを返す
    auto calc = [&](int l, int r) -> pair<ll, BIT<int>> {
        // 座圧
        vector<int> z(r - l);
        for (int i = l; i < r; ++i) {
            z[i - l] = a[i];
        }
        sort(z.begin(), z.end());
        z.erase(unique(z.begin(), z.end()), z.end());
        for (int i = l; i < r; ++i) {
            a[i] = lower_bound(z.begin(), z.end(), a[i]) - z.begin();
        }
        ll inv = 0;
        BIT<int> bit(z.size());
        for (int i = l; i < r; ++i) {
            inv += (i - l - bit.sum(a[i] + 1));
            bit.add(a[i], 1);
        }
        return {inv, bit};
    };

    // setで区間を管理 [l, r)
    set<pair<int, int>> st;
    st.insert({0, n});

    // 転倒数の値を管理
    multiset<ll> mst;

    // 初期化
    auto init = calc(0, n);
    mst.insert(init.first);
    bit_memo[0] = init.second;

    for (int i = 0; i < n; ++i) {
        ll val = *mst.rbegin();
        mst.erase(mst.find(val));
        cout << val << " ";

        ll mid;
        cin >> mid;
        mid = (mid ^ val) - 1;

        auto it = st.lower_bound({mid, 1e9});
        auto [l, r] = *(--it);
        st.erase(it);

        // 左端を消す場合
        if (l == mid) {
            if (mid + 1 != r) {
                val -= bit_memo[l].sum(a[l]);
                bit_memo[l].add(a[l], -1);
                swap(bit_memo[l], bit_memo[l + 1]);
                st.insert({l + 1, r});
                mst.insert(val);
            }
            continue;
        }
        // 右端を消す場合
        if (mid + 1 == r) {
            val -= (r - l) - bit_memo[l].sum(a[r - 1] + 1);
            bit_memo[l].add(a[r - 1], -1);
            st.insert({l, r - 1});
            mst.insert(val);
            continue;
        }
        // 区間が2つに分かれる場合
        if (mid - l <= r - mid) {
            for (int j = l; j <= mid; ++j) {
                val -= bit_memo[l].sum(a[j]);
                bit_memo[l].add(a[j], -1);
            }
            swap(bit_memo[l], bit_memo[mid + 1]);
            st.insert({mid + 1, r});
            mst.insert(val);
            auto nxt = calc(l, mid);
            bit_memo[l] = nxt.second;
            st.insert({l, mid});
            mst.insert(nxt.first);
        } else {
            for (int j = r - 1; j >= mid; --j) {
                val -= (j + 1 - l) - bit_memo[l].sum(a[j] + 1);
                bit_memo[l].add(a[j], -1);
            }
            st.insert({l, mid});
            mst.insert(val);
            auto nxt = calc(mid + 1, r);
            bit_memo[mid + 1] = nxt.second;
            st.insert({mid + 1, r});
            mst.insert(nxt.first);
        }
    }
    cout << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> q;
    while (q--) {
        slv();
    }
}

詳細信息

Test #1:

score: 0
Runtime Error

input:

3
5
4 3 1 1 1
5 4 5 3 1
10
9 7 1 4 7 8 5 7 4 8
21 8 15 5 9 2 4 5 10 6
15
4 8 8 1 12 1 10 14 7 14 2 9 13 10 3
37 19 23 15 7 2 10 15 2 13 4 5 8 7 10

output:


result: