Гірляндочка#12286

Гірляндочка (Розбір)

Автор задачі:	Андрій Холод (Connect)
Підготовлено:	Андрій Холод (Connect)
Розбір:	Андрій Холод (Connect)

Рішення

Давайте переформолюємо задачу. Наша операція це побітовий XOR на префіксі. Тоді оскільки при перестановці порядку операцій XOR результат не зміниться нам достатньо перевірити умову лише для будь якої однієї перестановки. Найзручніше це зробити для відсортованого порядку.

Давайте відсортуємо операції в порядку зростання довжини префікса. Тоді нам дуже легко відслідковувати яка кількість операцій змінить елемент на позиції $i$ . Оскільки при парній кількості операцій XOR значення не зміниться тоді нам достатньо лише перевіряти парність кількості операцій які змінюються значення $i$ та значення яке мали лисички.

Асимптотика рішення $O$ ( $n \cdot l o g (n)$ 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++