QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#167080 | #7108. Couleur | ikefumy | WA | 0ms | 3548kb | C++20 | 5.2kb | 2023-09-07 01:39:42 | 2023-09-07 01:39:42 |
Judging History
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'