QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#875614 | #7861. Inverse Topological Sort | kian2009 | WA | 1ms | 3712kb | C++14 | 1.1kb | 2025-01-29 23:53:18 | 2025-01-29 23:53:20 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
int n, a[MAXN], b[MAXN], ind[MAXN];
void input() {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++) {
cin >> b[i];
ind[b[i]] = i;
}
}
void findAns() {
vector<pair<int, int>> res;
int mi = -1, ma = -1, x = -1;
bool f = false;
for (int i = 1; i <= n; i++) {
if (!f) {
if (a[i] == b[i]) {
if (i != 1)
res.push_back({a[i - 1], a[i]});
continue;
}
if (a[i] > b[i]) {
cout << "NO" << endl;
return;
}
mi = a[i];
ma = b[i];
x = mi;
f = true;
if (i != 1) {
for (int j = i; j <= n; j++)
res.push_back({a[i - 1], a[j]});
}
continue;
}
if (a[i] < mi || a[i] > ma) {
if (ind[x] >= ind[a[i]]) {
cout << "NO" << endl;
return;
}
res.push_back({x, a[i]});
}
if (ind[a[i]] < ind[x])
x = a[i];
}
cout << "YES" << endl << res.size() << endl;
for (auto p : res)
cout << p.first << " " << p.second << endl;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
input();
findAns();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3712kb
input:
3 1 2 3 1 2 3
output:
YES 2 1 2 2 3
result:
ok n=3
Test #2:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
3 1 2 3 3 2 1
output:
YES 0
result:
ok n=3
Test #3:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
3 3 2 1 1 2 3
output:
NO
result:
ok n=3
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3712kb
input:
10 6 8 9 4 1 3 7 5 10 2 8 6 9 10 4 7 5 3 2 1
output:
YES 7 8 9 8 4 8 1 8 3 8 5 8 10 8 2
result:
wrong answer wrong solution