Garlend#12286

Garlend (Həll təhlili)

Məsələnin müəllifi:	Andrey Xolod (Connect)
Hazırlayan:	Andrey Xolod (Connect)
Təhlil:	Andrey Xolod (Connect)

Həll

Gəlin məsələni yenidən formalaşdıraq. Bizim əməliyyat — prefiks üzərində bitlik XOR-dur. XOR əməliyyatlarının yerinin dəyişməsi nəticəyə təsir etmədiyi üçün, şərti yalnız bir istənilən permutasiya üçün yoxlamaq kifayətdir. Bunu etmək üçün ən əlverişli seçim əməliyyatları prefiks uzunluğuna görə artan sırada sort etməkdir.

Əməliyyatları prefiks uzunluğuna görə sort etdikdən sonra, hansı əməliyyatların $i$ mövqeyinə təsir etdiyini izləmək çox asanlaşır. Çünki cüt sayda XOR əməliyyatı dəyəri dəyişmir, buna görə də mövqe $i$ üçün əməliyyatların sayının cüt və ya tək olmasını yoxlamaq və bunu tülkülərin gözlədiyi dəyərlə müqayisə etmək kifayətdir.

Həllin asimptotik mürəkkəbliyi — $O (n \cdot lo g n)$ O(n \cdot \log n).

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define endl '\n'

const ll clasik = 1e6+17;

ll df[clasik];

ll p[clasik];

void solve() {

    ll n;

    cin>>n;
    ll k;

    cin>>k;
    for (int i = 1 ; i <=n ; i++) {
        cin>>df[i];
    }

    for (int i = 1 ; i<=k ; i++) {
        cin>>p[i];
    }

    sort(p+1 , p+1+k);

    ll cnt = k , p1 = 1;

    for (int i = 1 ; i<=n ; i++) {
        if (cnt%2 != df[i]) {
            cout<<"No"<<endl;
            return;
        }
        while (p1<=k && p[p1] <= i) {
            p1++;
            cnt--;
        }
    }

    cout<<"Yes"<<endl;

    return;

}  

signed main() {
    speed;
    int test;
    cin>>test;
    while (test--) solve();
    return 0;
}

C++