/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 532.0 KiB
#2 Wrong Answer 1ms 532.0 KiB
#3 Wrong Answer 36ms 708.0 KiB

Code

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

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];

        // Any array of size ≤2 always works
        if (n <= 2) {
            cout << "Yes\n";
            continue;
        }

        // Helper to do the “A peaks over B?” check
        auto check = [&](const vector<ll>& X, const vector<ll>& Y) {
            // X will be our “peak” array; Y the “neighbors”
            // 1) max‑heap for X so we can put the LARGEST in the middle
            priority_queue<ll>   pqX(X.begin(), X.end());
            // 2) min‑heap for Y so we can put the SMALLEST around
            priority_queue<ll, vector<ll>, greater<ll>> pqY(Y.begin(), Y.end());

            vector<ll> x(n), y(n);

            // 1. carve out x[1..n-2] = next-largest, then x[n-1], x[0]
            for (int i = 1; i < n-1; i++){
                x[i] = pqX.top(); 
                pqX.pop();
            }
            x[n-1] = pqX.top(); pqX.pop();
            x[0]   = pqX.top(); pqX.pop();

            // 2. fill y by alternating indices 0,2,4... then 1,3,5...
            //    (so that neighbors of every middle spot are as small as possible)
            int idx = 0;
            while (!pqY.empty()){
                y[idx] = pqY.top(); 
                pqY.pop();
                idx += 2;
                if (idx >= n) idx = 1;
            }

            // 3. check cross-peak: x[i] > y[i-1] && x[i] > y[i+1] for 1 ≤ i ≤ n-2
            for (int i = 1; i < n-1; i++){
                if (!(x[i] > y[i-1] && x[i] > y[i+1]))
                    return false;
            }
            return true;
        };

        // Try A peaks over B or B peaks over A
        cout << (check(A,B) || check(B,A) ? "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:28:53
Judged At
2025-06-13 16:28:53
Judged By
Score
0
Total Time
36ms
Peak Memory
708.0 KiB