QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#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

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

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'