Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cmath>
- #include <algorithm>
- #include <vector>
- #include <set>
- using namespace std;
- #define pii pair<int, int>
- struct person {
- int exp;
- int type;
- int pos;
- person() {
- this->exp = -1;
- this->type = -1;
- this->pos = -1;
- }
- person(int e, int t, int p) {
- this->exp = e;
- this->type = t;
- this->pos = p;
- }
- };
- struct dance {
- int dif;
- person first;
- person second;
- dance() {
- this->dif = -1;
- this->first = { -1, -1, -1 };
- this->second = { -1, -1, -1 };
- }
- dance(int d, person a, person b) {
- this->dif = d;
- this->first = a;
- this->second = b;
- }
- };
- bool operator<(person a, person b) {
- if (a.exp == b.exp) {
- if (a.pos == b.pos) {
- return a.type < b.type;
- }
- return a.pos < b.pos;
- }
- return a.exp < b.exp;
- }
- bool operator!=(person a, person b) {
- return (a.exp != b.exp || a.type != b.type || a.pos != b.pos);
- }
- bool operator==(person a, person b) {
- return (a.exp == b.exp && a.type == b.type && a.pos == b.pos);
- }
- bool operator<(dance a, dance b) {
- if (a.dif == b.dif) {
- if (a.first == b.first) {
- return a.second < b.second;
- }
- return a.first < b.first;
- }
- return a.dif < b.dif;
- }
- int main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0); cout.tie(0);
- int n;
- cin >> n;
- vector <int> boys(n), girls(n);
- for (int i = 0; i < n; ++i) {
- cin >> boys[i];
- }
- for (int i = 0; i < n; ++i) {
- cin >> girls[i];
- }
- set <person> order;
- for (int i = 0; i < n; ++i) {
- order.insert({ boys[i], 1, i + 1 });
- }
- for (int i = 0; i < n; ++i) {
- order.insert({ girls[i], 2, i + 1 });
- }
- set <dance> pairs;
- for (auto it = ++order.begin(); it != order.end(); ++it) {
- dance cur;
- cur.dif = (*it).exp - (*(--it)).exp;
- ++it;
- cur.first = *(--it);
- ++it;
- cur.second = *it;
- pairs.insert(cur);
- }
- vector <pii> ans;
- person last = { 1000000001, -1, -1 };
- order.insert(last);
- /*for (person x : order) {
- cout << x.exp << " " << x.type << " " << x.pos << "\n";
- }
- for (dance x : pairs) {
- cout << x.dif << " " << x.first.pos << " " << x.second.pos << "\n";
- }*/
- while (!pairs.empty()) {
- dance cur = *pairs.begin();
- //cout << "ok " << cur.dif << " " << cur.first.type << "-" << cur.first.pos << " " << cur.second.type << "-" << cur.second.pos << "\n";
- if (cur.first.type != cur.second.type && order.find(cur.first) != order.end() && order.find(cur.second) != order.end()) {
- if (cur.first.type == 1) {
- ans.push_back({ cur.first.pos, cur.second.pos });
- }
- else {
- ans.push_back({ cur.second.pos, cur.first.pos });
- }
- if (order.find(cur.first) != order.begin() && (*(++order.find(cur.second))) != last) {
- dance now;
- now.first = (*(--order.find(cur.first)));
- now.second = (*(++order.find(cur.second)));
- now.dif = now.second.exp - now.first.exp;
- //cout << "insert: " << now.dif << " " << now.first.type << "-" << now.first.pos << " " << now.second.type << "-" << now.second.pos << "\n";
- pairs.insert(now);
- }
- order.erase(cur.first);
- order.erase(cur.second);
- }
- pairs.erase(cur);
- }
- for (auto p : ans) {
- cout << p.first << " " << p.second << "\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement