QOJ.ac

QOJ

The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#520409	#5466. Permutation Compression	no_RED_no_DEAD	WA	2ms	11876kb	C++20	1.3kb	2024-08-15 13:34:45	2024-08-15 13:34:45

Judging History

This is the latest submission verdict.

[2024-08-15 13:34:45]
Judged

Verdict: WA
Time: 2ms
Memory: 11876kb

Show

[2024-08-15 13:34:45]
Submitted

answer

#include "bits/stdc++.h"
using namespace std;
using ll = long long;

const ll N = 1e6 + 1;
const ll M = 1e9 + 7;

ll n, m, k;
ll a[N], b[N], l[N];
ll pp[N], tmp[N];

bool inorder() {
    ll j = 1;
    for (int i = 1; i <= n; i ++)
        if (a[i] == b[j]) j ++;
    return (j >= m + 1);
}

void buffalo() {
    for (int i = 1; i <= n; i ++) pp[a[i]] = 1;
    for (int i = 1; i <= m; i ++) pp[b[i]] = 0; 

    sort(l + 1, l + k + 1); k = n - m;
    for (int i = k; i >= 1; i --) {
        bool ok = 0; ll del;
        for (int j = l[i]; j <= n; j ++) {
            ll lc = j - l[i] + 1, rc = j, mx = -1e18;
            for (int x = lc; x <= rc; x ++) mx = max(mx, a[x]);
            if (pp[mx] == 1) {ok = 1; del = mx; break;}
        }
        if (!ok) {cout << "NO\n"; return;}
    }
    cout << "YES\n";
}

void doTest(ll testID) {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    for (int i = 1; i <= m; i ++) cin >> b[i];
    for (int i = 1; i <= k; i ++) cin >> l[i];

    if (k + m < n) {cout << "NO\n"; return;}
    if (!inorder()) {cout << "NO\n"; return;}
    
    buffalo();
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    int test = 1; 
    cin >> test;
    for (int _ = 1; _ <= test; _ ++) doTest(test);
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 2ms

memory: 11876kb

input:

output:

YES
YES
NO

result:

ok 3 lines

Test #2:

score: -100

Wrong Answer

time: 2ms

memory: 11776kb

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

result:

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