POI Task Rooks

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

vector<int> solve(vector<int> x, vector<int> y) {
    size_t n = x.size();
    vector<pair<pair<int, int>, int>> v(n);
    for (size_t i = 0; i < n; ++i) v[i] = {{y[i], x[i]}, i};
    sort(v.begin(), v.end());
    set<int> positions;
    for (size_t i = 1; i <= n; ++i) positions.insert(i);

    vector<int> ans(n);
    for (auto [pr, i] : v) {
        auto [r, l] = pr;
        set<int>::iterator it = positions.lower_bound(l);
        if (it == positions.end() || *it > r) return {};
        ans[i] = *it;
        positions.erase(it);
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    vector<int> a(n), b(n), c(n), d(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
    }
    vector<int> e = solve(a, c), f = solve(b, d);
    if (e.empty() || f.empty()) cout << "NIE\n";
    else {
        for (int i = 0; i < n; ++i) {
            cout << e[i] << ' ' << f[i] << '\n';
        }
    }
    return 0;
}