Garland#12286

Garland (Editorial)

Author of the problem:	Andrii Kholod (Connect)
Prepared by:	Andrii Kholod (Connect)
Analysis:	Andrii Kholod (Connect)

Solution

Let us reformulate the problem. Our operation is a bitwise XOR on a prefix. Since the result of XOR does not depend on the order of applying the operations, it is enough to check the condition for any single permutation. The most convenient option is to check it for the sorted order.

Let us sort the operations in non-decreasing order of the prefix length. Then it becomes very easy to track how many operations will change the element at position $i$ . Since an even number of XOR operations does not change the value, it is enough to check the parity of the operations affecting position $i$ and compare it with the value expected by the foxes.

The time complexity of the solution is $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++