QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#372883 | #5277. Limited Swaps | FOY# | RE | 1ms | 3592kb | C++14 | 1.6kb | 2024-03-31 20:14:45 | 2024-03-31 20:14:55 |
Judging History
answer
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;
using vi = vector<int>;
using vpi = vector<pair<int, int>>;
int main() {
int n; cin >> n;
vi a(n);
vi b(n);
vi aplace(n);
vi bplace(n);
vpi shit;
for (int i = 0; i < n; i++) {
cin >> a[i];
aplace[a[i]] = i;
}
for (int i = 0; i < n; i++) {
cin >> b[i];
bplace[b[i]] = i;
shit.push_back({i, b[i]});
}
sort(shit.begin(), shit.end(), greater<>());
for (int i = 0; i < n-1; i++) {
if ((aplace[i] - aplace[i-1])*(bplace[i] - bplace[i-1]) < 0) {
// opposite order
cout << -1 << endl;
return 0;
}
}
// can be done
// what goes in last place?
// just order by descending last position
vi ans;
for (int i = 0; i < n; i++) {
int x = shit[i].second;
int idx = 0;
for (; idx < n; idx++) {
if (a[idx] == x) break;
}
while (idx < bplace[x]) {
ans.push_back(idx);
assert(idx < n);
assert(abs(a[idx] - a[idx+1]) >= 2);
swap(a[idx], a[idx+1]);
idx++;
}
while (idx > bplace[x]) {
assert(idx > 0);
assert(abs(a[idx] - a[idx-1]) >= 2);
ans.push_back(idx-1);
swap(a[idx], a[idx-1]);
idx--;
}
}
cout << ans.size() << endl;
for (int x : ans) cout << x+1 << ' ';
if (ans.size()) cout << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3452kb
input:
5 1 3 5 2 4 3 5 1 4 2
output:
3 4 1 2
result:
ok OK, found solution, n = 5, ops = 3
Test #2:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
4 1 2 3 4 4 3 2 1
output:
-1
result:
ok OK, no solution
Test #3:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
1 1 1
output:
0
result:
ok OK, found solution, n = 1, ops = 0
Test #4:
score: -100
Runtime Error
input:
2 1 2 2 1