QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #761568 | #2296. Exchange Students | KarL06 | WA | 2ms | 16040kb | C++20 | 3.0kb | 2024-11-19 00:52:13 | 2024-11-19 00:52:14 |
Judging History
answer
#ifdef DEBUG
#include"bits/dbg.h"
#else
#define dbg(...)
#endif
#include"bits/stdc++.h"
#define int long long
#define P pair<int,int>
#define fi first
#define se second
using namespace std;
const int maxn = 3e5+5;
P p[maxn]; //{weight, position}
P ord[maxn];
int a[maxn], b[maxn];
int n;
map< int,set<int> > mp;
int t1[maxn]; // original
int t2[maxn]; // new
int lowbit (int x) {
return x&(-x);
}
void add (int x, int v, int* bit) {
if (x == 0) return;
for (int i=x;i<maxn;i+=lowbit(i)) {
bit[i] += v;
}
}
int query (int x, int* bit) {
int ans = 0;
for (int i=x;i>=1;i-=lowbit(i)) {
ans += bit[i];
}
return ans;
}
signed main () {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i=1;i<=n;i++) {
cin >> a[i];
}
for (int i=1;i<=n;i++) {
cin >> b[i];
mp[b[i]].insert(i);
}
for (int i=1;i<=n;i++) {
int id = *mp[a[i]].begin();
mp[a[i]].erase(id);
p[i] = {a[i], id};
ord[i] = {a[i], i};
//dbg(p[i]); // OK
}
sort(ord+1, ord+n+1);
for (int i=1;i<=n;i++) {
add(i, 1, t1);
add(i, 1, t2);
}
int sum = 0;
vector<P> prt;
for (int i=1;i<=n;i++) {
int j = ord[i].se;
int k = p[j].se;
int v1 = query(k, t1);
int v2 = query(j, t2);
sum += abs(v1-v2);
dbg(v1-v2, i); // OK
if (prt.size() <= 2e5) {
int l = 1;
int r = n;
int x = -1;
while (l <= r) {
int mid = (l+r)/2;
if (query(mid, t1) >= v2) {
x = mid;
r = mid-1;
}
else {
l = mid+1;
}
}
int y = k;
dbg(x, y);
// need to skip fixed positions
if (x > y) {
int pre = x;
for (int j=x-1;j>=y;j--) {
if (query(j, t1)-query(j-1, t1) == 0) {
continue;
}
if (prt.size() < 2e5) {
prt.push_back({j, pre});
pre = j;
}
}
}
if (x < y) {
int pre = x;
for (int j=x+1;j<=y;j++) {
if (query(j, t1)-query(j-1, t1) == 0) {
continue;
}
if (prt.size() < 2e5) {
prt.push_back({j, pre});
pre = j;
}
}
}
}
add(k, -1, t1);
add(j, -1, t2);
}
assert (prt.size() <= 2e5);
cout << sum << "\n";
for (P pt: prt) {
cout << pt.fi << " " << pt.se << "\n";
}
}
/*
5
2 2 2 2 1
1 2 2 2 2
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 13776kb
input:
1 279122803 279122803
output:
0
result:
ok good
Test #2:
score: 0
Accepted
time: 2ms
memory: 13820kb
input:
2 212545283 896408766 212545283 896408766
output:
0
result:
ok good
Test #3:
score: 0
Accepted
time: 0ms
memory: 13848kb
input:
4 3 1 2 4 4 2 1 3
output:
2 3 2 4 1
result:
ok good
Test #4:
score: 0
Accepted
time: 2ms
memory: 15880kb
input:
6 5 1 2 3 4 6 6 4 3 2 1 5
output:
7 3 2 4 3 5 4 3 2 4 3 3 2 6 1
result:
ok good
Test #5:
score: 0
Accepted
time: 2ms
memory: 16040kb
input:
2 2 1 1 2
output:
1 1 2
result:
ok good
Test #6:
score: 0
Accepted
time: 0ms
memory: 13768kb
input:
4 3 2 2 1 2 1 2 3
output:
4 3 4 2 3 1 3 3 4
result:
ok good
Test #7:
score: 0
Accepted
time: 2ms
memory: 13792kb
input:
9 708443928 333343028 130113530 997808421 299459189 845949632 647591888 681805948 468112900 299459189 997808421 130113530 845949632 647591888 681805948 468112900 708443928 333343028
output:
13 4 5 2 4 1 2 5 4 6 5 7 6 8 7 9 8 7 8 5 6 6 8 4 2 8 4
result:
ok good
Test #8:
score: 0
Accepted
time: 1ms
memory: 13780kb
input:
3 732684994 647116406 457545388 732684994 647116406 457545388
output:
0
result:
ok good
Test #9:
score: 0
Accepted
time: 2ms
memory: 13788kb
input:
4 105385396 776935185 411665343 757889658 776935185 411665343 757889658 105385396
output:
3 2 1 3 2 4 3
result:
ok good
Test #10:
score: 0
Accepted
time: 0ms
memory: 13796kb
input:
4 1 2 2 1 2 2 1 1
output:
2 2 1 3 2
result:
ok good
Test #11:
score: -100
Wrong Answer
time: 1ms
memory: 13776kb
input:
10 1 2 1 2 1 1 2 2 2 1 1 2 2 2 2 1 1 2 1 1
output:
8 4 3 5 4 6 5 5 4 7 5 5 4 8 5 9 8
result:
wrong answer Invalid swap