QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#648418#5466. Permutation CompressioncrychicRE 0ms3488kbC++172.1kb2024-10-17 18:54:202024-10-17 18:54:21

Judging History

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

  • [2024-10-17 18:54:21]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3488kb
  • [2024-10-17 18:54:20]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int N = 2e5 + 10;

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    std::vector<int> posss(n + 1), hass(n + 1);
    for(int i = 1, x; i <= n; i ++ ) {
        cin >> x;
        posss[x] = i;
    }
    vector<int> a(m + 1);
    for(int i = 1, x; i <= m; i ++ ) {
        cin >> x;
        hass[x] = 1;
        a[i] = x;
    }
    for(int i = 1; i < m; i ++ ) {
        if(posss[a[i + 1]] < posss[a[i]]) {
            cout << "NO\n";
            return ;
        }
    }
    vector<int> b(k + 1), used(k + 1);
    for(int i = 1, x; i <= k; i ++ ) {
        cin >> x;
        b[i] = x;
    }
    bool fg = 0;
    vector<int> vis(n + 2), vis2(n + 2);
    vis[n + 1] = vis[0] = 1;
    vector<int> need_del(n + 1);
    for(int i = n; i >= 1; i -- ) {
        if(!hass[i]) {
            int l = 0, r = 0;
            for(int j = posss[i]; j <= n + 1; j ++ ) {
                if(vis[j]) {
                    r = j;
                    break;
                }
            }
            for(int j = posss[i]; j >= 0; j -- ) {
                if(vis[j]) {
                    l = j;
                    break;
                }
            }
            int w = r - l - 1;
            for(int j = l + 1; j < r; j ++ ) {
                if(vis2[j]) w -- ;
            }
            bool fg2 = 1;
            for(int j = k; j >= 1; j -- ) {
                if(!used[j] && b[j] <= w) {
                    used[j] = 1;
                    fg2 = 0;
                    break;
                }
            }
            if(fg2) {
                fg = 1;
                break;
            } else {
                vis2[posss[i]] = 1;
                // need_del[posss[i]] = 1;
            }
        } else {
            vis[posss[i]] = 1;
        }
    }
    if(fg) {
        cout << "NO\n";
    } else {
        cout << "YES\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    int t = 1;
    cin >> t;
    while(t -- ) {
        solve();
    }

    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3488kb

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
Runtime Error

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:


result: