QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#167080#7108. CouleurikefumyWA 0ms3548kbC++205.2kb2023-09-07 01:39:422023-09-07 01:39:42

Judging History

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

  • [2023-09-07 01:39:42]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3548kb
  • [2023-09-07 01:39:42]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define db double
#define pii pair<int,int>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define pll pair<ll,ll>
#define ti3 tuple<int,int,int>
#define int128 __int128_t
#define pii128 pair<int128,int128>
const int inf = 1 << 30;
const ll linf = 1e18;
const ll mod = 1e9 + 7;
const db EPS = 1e-10;
const db pi = acos(-1);
template<class T> bool chmin(T& x, T y){
    if(x > y) {
        x = y;
        return true;
    } else return false;
}
template<class T> bool chmax(T& x, T y){
    if(x < y) {
        x = y;
        return true;
    } else return false;
}

// overload macro
#define CAT( A, B ) A ## B
#define SELECT( NAME, NUM ) CAT( NAME, NUM )

#define GET_COUNT( _1, _2, _3, _4, _5, _6 /* ad nauseam */, COUNT, ... ) COUNT
#define VA_SIZE( ... ) GET_COUNT( __VA_ARGS__, 6, 5, 4, 3, 2, 1 )

#define VA_SELECT( NAME, ... ) SELECT( NAME, VA_SIZE(__VA_ARGS__) )(__VA_ARGS__)

// rep(overload)
#define rep( ... ) VA_SELECT(rep, __VA_ARGS__)
#define rep2(i, n) for (int i = 0; i < int(n); i++)
#define rep3(i, a, b) for (int i = a; i < int(b); i++)
#define rep4(i, a, b, c) for (int i = a; i < int(b); i += c)

// repll(overload)
#define repll( ... ) VA_SELECT(repll, __VA_ARGS__)
#define repll2(i, n) for (ll i = 0; i < ll(n); i++)
#define repll3(i, a, b) for (ll i = a; i < ll(b); i++)
#define repll4(i, a, b, c) for (ll i = a; i < ll(b); i += c)

// rrep(overload)
#define rrep( ... ) VA_SELECT(rrep, __VA_ARGS__)
#define rrep2(i, n) for (int i = n - 1; i >= 0; i--)
#define rrep3(i, a, b) for (int i = b - 1; i >= a; i--)
#define rrep4(i, a, b, c) for (int i = b - 1; i >= a; i -= c)

// rrepll(overload)
#define rrepll( ... ) VA_SELECT(rrepll, __VA_ARGS__)
#define rrepll2(i, n) for (ll i = n - 1; i >= 0ll; i--)
#define rrepll3(i, a, b) for (ll i = b - 1; i >= ll(a); i--)
#define rrepll4(i, a, b, c) for (ll i = b - 1; i >= ll(a); i -= c)

// for_earh
#define fore(e, v) for (auto&& e : v)

// vector
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

template<class T>
struct BIT{
    int N;
    vector<T> bit;
    BIT(int n = 0) : N(n), bit(n + 1, 0) {}

    void add(int i, T x){
        while(i <= N){
            bit[i] += x;
            i += i & -i;
        }
    }

    T sum(int i){
        i = clamp(i, 0, N);
        T s = 0;
        while(i > 0){
            s += bit[i];
            i -= i & -i;
        }
        return s;
    }

    T sum(int l1, int r2){
        return sum(r2) - sum(l1 - 1);
    }
};

void solve() {
    int n;
    ll p;
    cin >> n;
    vector<ll> a(n + 1);
    rep(i, 1, n + 1) cin >> a[i];
    
    vector<BIT<ll>> bits(n + 2);
    vector<vector<int>> nums(n + 2);
    vector<ll> invs(n + 2);
    multiset<ll> mst;
    set<int> unav;

    unav.insert(0);
    unav.insert(n + 1);
    bits[1] = BIT<ll>(n);
    rep(i, 1, n + 1) {
        invs[1] += bits[1].sum(a[i] + 1, n);
        bits[1].add(a[i], 1);
        nums[1].emplace_back(i);
    }
    mst.insert(invs[1]);

    rep(_, n) {
        cout << *mst.rbegin() << " \n"[_ == n - 1];
        cin >> p;
        p ^= *mst.rbegin();
        auto it = unav.lower_bound(p);
        int r2 = *it - 1, l1 = *(--it) + 1;
        int l2 = p + 1, r1 = p - 1;

        mst.erase(mst.find(invs[l1]));

        if (r1 - l1 < r2 - l2) {
            swap(bits[l1], bits[l2]);
            swap(nums[l1], nums[l2]);
            swap(invs[l1], invs[l2]);
            swap(r1, r2);
            swap(l1, l2);
        }
        
        nums[l2].emplace_back(p);
        rep(i, l2, r2 + 1) {
            nums[l2].emplace_back(a[i]);
            int it1 = lower_bound(all(nums[l1]), a[i]) - nums[l1].begin() + 1;
            bits[l1].add(it1, -1);
        }
        nums[l2].erase(unique(all(nums[l2])), nums[l2].end());

        int m = nums[l2].size();
        bits[l2] = BIT<ll>(m);

        rep(i, l2, r2 + 1) {
            int it1 = lower_bound(all(nums[l1]), a[i]) - nums[l1].begin() + 1;
            int it2 = lower_bound(all(nums[l2]), a[i]) - nums[l2].begin() + 1;
            bits[l2].add(it2, 1);
            invs[l2] += bits[l2].sum(it2 + 1, m);
            invs[l1] -= bits[l2].sum(it2 + 1, m);
            if (r1 < r2) {
                invs[l1] -= bits[l1].sum(it1 + 1, nums[l1].size());
            } else {
                invs[l1] -= bits[l1].sum(it1 - 1);
            }
        }

        int it1 = lower_bound(all(nums[l1]), a[p]) - nums[l1].begin() + 1;
        int it2 = lower_bound(all(nums[l2]), a[p]) - nums[l2].begin() + 1;
        bits[l1].add(it1, -1);
        if (r1 < r2) {
            invs[l1] -= bits[l1].sum(it1 + 1, nums[l1].size()) + bits[l2].sum(it2 - 1);
        } else {
            invs[l1] -= bits[l1].sum(it1 - 1) + bits[l2].sum(it2 + 1, m);
        }

        if (l1 <= r1) mst.insert(invs[l1]);
        if (l2 <= r2) mst.insert(invs[l2]);
        unav.insert(p);
    }
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3548kb

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:

7 0 0 0 0
20 11 6 2 0 0 0 0 0 0
42 31 21 14 14 4 1 1 1 0 0 0 0 0 0

result:

wrong answer 2nd lines differ - expected: '20 11 7 2 0 0 0 0 0 0', found: '20 11 6 2 0 0 0 0 0 0'