/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 532.0 KiB
#2 Wrong Answer 1ms 324.0 KiB
#3 Wrong Answer 28ms 580.0 KiB

Code

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

bool can_peak(const vector<ll>& X, const vector<ll>& Y) {
    int n = X.size();
    if (n <= 2) return true;
    // We want X[i] > Y[i-1] && X[i] > Y[i+1] for all 1 <= i <= n-2
    // Greedy: put largest X's in the middle
    vector<ll> x = X, y = Y;
    sort(x.begin(), x.end(), greater<ll>());  // largest first
    sort(y.begin(), y.end());                  // smallest first

    // We will try to match x[0]..x[n-1] to positions:
    // position 1,2,...,n-2 in order
    // so that x[k] > y[k] and x[k] > y[k+2]
    for (int i = 1; i < n-1; i++) {
        // We need some unused x[j] > y[i-1] and > y[i+1].
        // Since x is sorted desc, and y asc, it's enough to check
        // x[i-1] against y[i-1] and y[i+1].
        // (Index-shift: the ith middle slot uses x[i-1].)
        if (!(x[i-1] > y[i-1] && x[i-1] > y[i+1]))
            return false;
    }
    return true;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<ll> A(n), B(n);
        for (int i = 0; i < n; i++) cin >> A[i];
        for (int i = 0; i < n; i++) cin >> B[i];

        // Try A peaking over B, or B peaking over A
        bool ok = can_peak(A, B) || can_peak(B, A);
        cout << (ok ? "Yes\n" : "No\n");
    }
    return 0;
}

Information

Submit By
Type
Submission
Problem
P1193 C. Roy and Peak Array
Contest
Brain Booster #10
Language
C++17 (G++ 13.2.0)
Submit At
2025-06-13 16:29:28
Judged At
2025-06-13 16:29:28
Judged By
Score
0
Total Time
28ms
Peak Memory
580.0 KiB