QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#794005	#5466. Permutation Compression	JustJie^#	WA	1ms	3652kb	C++20	2.4kb	2024-11-30 09:11:25	2024-11-30 09:11:26

Judging History

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

[2024-11-30 09:11:26]
评测

测评结果：WA
用时：1ms
内存：3652kb

查看

[2024-11-30 09:11:25]
提交

answer

/***************************************************************************************************
 * author : Jie Chen (4th Year CS)
 * school : Rochester Institute of Technology
 * created: 11.29.2024 19:49:43
****************************************************************************************************/
#include "bits/stdc++.h"

using namespace std;

using i64 = long long;
using Segment = array<int, 2>;

void work(int tc) {
    int n, m, k;
    cin >> n >> m >> k;

    vector<int> a(n), pos(n), b(m);

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;
        pos[a[i]] = i;
    }
    for (int i = 0; i < m; i++) {
        cin >> b[i];
        b[i]--;
    }

    multiset<int> t;
    for (int i = 0; i < k; i++) {
        int x;
        cin >> x;
        t.insert(x);
    }

    const auto get = [&](int x) {
        return pos[x];
    };

    int cur = 0;
    vector<bool> del(n);
    for (int i = 0; i < m - 1; i++) {
        int l = get(b[i]);
        int r = get(b[i + 1]);
        if (r < l || l < cur) {
            cout << "NO\n";
            return;
        }
        cur = l;
        for (int j = l + 1; j < r; j++) {
            del[a[j]] = true;
        }
    }

    set<Segment> s;
    s.insert({0, n - 1});
    for (int tr = n - 1; tr >= 0; tr--) {
        int p = get(tr);
        // cout << tr << " " << p << "\n";
        auto it = prev(s.upper_bound({p, n + 1}));
        auto [l, r] = *it;
        int sz = r - l + 1;
        if (del[tr]) {
            // cout << sz << "\n";
            if (t.empty()) {
                cout << "NO\n";
                return;
            }
            auto it2 = t.upper_bound(sz);
            if (it2 == t.begin()) {
                cout << "NO\n";
                return;
            }
            it2--;
            t.erase(it2);
        }
        s.erase(it);
        if (sz > 1) {
            if (p == l) {
                s.insert({l + 1, r});
            } else if (p == r) {
                s.insert({l, r - 1});
            } else {
                s.insert({l, p - 1});
                s.insert({p + 1, r});
            }
        }
    }
    cout << "YES\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    for (int t = 1; T--; t++) {
        work(t);
    }
}

// ~ JustJie

源文件, 语言: C++20

详细

Test #1:

score: 100

Accepted

time: 1ms

memory: 3616kb

input:

output:

YES
YES
NO

result:

ok 3 lines

Test #2:

score: -100

Wrong Answer

time: 0ms

memory: 3652kb

input:

100
2 1 2
2 1
2
1 1
2 1 2
1 2
1
2 2
2 1 1
1 2
1
2
6 1 5
3 4 2 5 6 1
3
5 2 1 1 1
6 1 6
2 1 3 6 4 5
1
4 1 2 2 1 4
3 3 2
2 1 3
2 1 3
2 2
1 1 1
1
1
1
1 1 1
1
1
1
2 1 2
2 1
2
1 2
4 4 3
2 1 3 4
2 1 3 4
4 3 1
1 1 1
1
1
1
6 5 1
6 2 5 4 3 1
6 2 4 3 1
4
1 1 1
1
1
1
6 5 3
3 6 1 4 5 2
3 6 1 4 2
3 3 4
4 3 4
3 4 ...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
NO
YES
YES
NO
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YE...

result:

wrong answer 23rd lines differ - expected: 'NO', found: 'YES'