QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#113362#5466. Permutation CompressionkemunikuWA 1ms3496kbC++2.7kb2023-06-17 10:44:132023-06-17 10:44:16

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-17 10:44:16]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3496kb
  • [2023-06-17 10:44:13]
  • Submitted

answer

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <queue>

std::vector<int> solve() {
    int N, M, K;
    std::cin >> N >> M >> K;
    
    std::vector<int> A(N), B(M), L(K);
    for (int i = 0; i < N; ++i)
        std::cin >> A[i];
    for (int i = 0; i < M; ++i)
        std::cin >> B[i];
    for (int i = 0; i < K; ++i)
        std::cin >> L[i];
    
    std::set<int> sB(B.begin(), B.end());
    std::vector<int> ok(N, -1);
    std::priority_queue<int, std::vector<int>, std::greater<int>> q;
    std::vector<int> v_to_i(N + 1, -1);
    for (int i = 0; i < N; ++i)
        v_to_i[A[i]] = i;
    
    std::vector<int> start(N + 1, -1);
    std::set<int> st;
    for (int i = N - 1; i >= 0; --i) {
        if (sB.count(A[i]) > 0) {
            while (!q.empty() && q.top() < A[i]) {
                int x = q.top();
                q.pop();
                ok[v_to_i[x]] = std::distance(st.begin(), st.lower_bound(x)) - start[x];
            }
        } else {
            q.push(A[i]);
            start[A[i]] = std::distance(st.begin(), st.lower_bound(A[i]));
        }
        st.insert(A[i]);
    }
    while (!q.empty()) {
        int x = q.top();
        q.pop();
        ok[v_to_i[x]] = std::distance(st.begin(), st.lower_bound(x)) - start[x];
    }
    
    q = std::priority_queue<int, std::vector<int>, std::greater<int>>();
    start.assign(N + 1, -1);
    st.clear();
    for (int i = 0; i < N; ++i) {
        if (sB.count(A[i]) > 0) {
            while (!q.empty() && q.top() < A[i]) {
                int x = q.top();
                q.pop();
                ok[v_to_i[x]] += std::distance(st.begin(), st.lower_bound(x)) - start[x];
            }
        } else {
            q.push(A[i]);
            start[A[i]] += std::distance(st.begin(), st.lower_bound(A[i]));
        }
        st.insert(A[i]);
    }
    while (!q.empty()) {
        int x = q.top();
        q.pop();
        ok[v_to_i[x]] += std::distance(st.begin(), st.lower_bound(x)) - start[x];
    }
    
    std::vector<int> li;
    for (int i = 0; i < N; ++i) {
        if (ok[i] != -1)
            li.push_back(ok[i]);
    }
    
    std::sort(li.begin(), li.end());
    std::sort(L.begin(), L.end());
    
    if (li.size() > L.size())
        return {0};
    
    for (int i = 0; i < li.size(); ++i) {
        if (li[i] < L[i])
            return {0};
    }
    
    return {1};
}

int main() {
    int T;
    std::cin >> T;
    
    for (int i = 0; i < T; ++i) {
        std::vector<int> result = solve();
        if (result[0] == 1)
            std::cout << "YES\n";
        else
            std::cout << "NO\n";
    }
    
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3496kb

input:

3
5 2 3
5 1 3 2 4
5 2
1 2 4
5 5 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
3 2 2
3 1 2
3 2
2 3

output:

YES
YES
NO

result:

ok 3 lines

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3420kb

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
NO
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
NO
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
Y...

result:

wrong answer 45th lines differ - expected: 'NO', found: 'YES'