Submission #70488235

---

Source Code Expand

#include <bits/stdc++.h>


using namespace std;


pair <int,int> getFingerprint(vector <int> &v) {
    int sum = 0, inv = 0;
    for (int i = 0; i < (int) v.size(); i++) {
        inv += v[i] * (i - sum);
        sum += v[i];
    }

    return {sum, inv};
}

vector <int> getPos(vector <int> &v) {
    vector <int> p;
    for (int i = 0; i < (int) v.size(); i++) {
        if (v[i]) {
            p.push_back(i);
        }
    }

    return p;
}

vector <vector<int>> solve(int n, vector <int> &vSource, vector <int> &vTarget) {
    int sum = 0;
    for (int &v : vSource) sum += v;

    if (sum > n - sum) {
        for (int i = 0; i < n; i++) {
            vSource[i] = 1 - vSource[i];
            vTarget[i] = 1 - vTarget[i];
        }
    }

    vector <int> pSource = getPos(vSource), pTarget = getPos(vTarget);

    deque <int> ids;
    vector <vector<int>> ans;

    for (int i = 0; i < (int) pSource.size(); i++) {
        if (pSource[i] == pTarget[i]) {
            continue;
        }

        if (!ids.empty()) {
            int j = ids.back();
            if (pSource[j] < pTarget[j] && pSource[i] > pTarget[i]) {
                int l = min(pTarget[j] - pSource[j], pSource[i] - pTarget[i]);

                ans.push_back({pSource[j], pSource[j] + l, pSource[i] - l, pSource[i]});

                pSource[j] += l;
                pSource[i] -= l;

                if (pSource[j] == pTarget[j]) {
                    ids.pop_back();
                    i--;
                    continue;
                }
            }
        }

        if (pSource[i] != pTarget[i]) {
            ids.push_back(i);
        }
    }

    while (!ids.empty()) {
        int j = ids[0], i = ids.back();
        int l = min(pSource[j] - pTarget[j], pTarget[i] - pSource[i]);

        ans.push_back({pSource[j] - l, pSource[j], pSource[i], pSource[i] + l});

        pSource[j] -= l;
        pSource[i] += l;

        if (pSource[j] == pTarget[j]) {
            ids.pop_front();
        }

        if (pSource[i] == pTarget[i]) {
            ids.pop_back();
        }
    }

    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector <int> a(n), b(n);

        for (int &ai : a) {
            cin >> ai;
        }

        for (int &bi : b) {
            cin >> bi;
        }

        if (getFingerprint(a) != getFingerprint(b)) {
            cout << "No\n";
        } else {
            cout << "Yes\n";

            auto ans = solve(n, a, b);
            cout << ans.size() << '\n';

            for (auto &v : ans) {
                for (int x : v) {
                    cout << x + 1 << ' ';
                }

                cout << '\n';
            }
        }
    }

    return 0;
}

Submission Info

Judge Result