Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- //подключает всю STL C++
- using namespace std;
- #define do(_, n) for(int _ = 1; _ < n + 1; _++)
- //упрощает работу с индексами
- #define _getchar_nolock getchar_unlocked
- //Без этого дефайна информатикс (GCC < 7.0.0) выдает ошибку
- long long FastIntInput() {
- long long a = 0;//Вводимое число
- char c = ' ';
- bool f = false;//Булево на a < 0
- while (!isdigit(c)){//Считываем то, что между цифрами
- c = _getchar_nolock();/*Как getchar(), но не блокирует
- во время работы потоки помимо cin, за счет чего работает быстрее*/
- if (c == '-')
- f = true;
- }
- while (isdigit(c)) {
- a = a * 10 + (c - '0');
- c = _getchar_nolock();
- }
- if (f)
- return -a;
- return a;
- }
- void debug(set<int> &b)
- {
- for(auto i : b)
- cout << i << ' ';
- cout << '\n';
- }
- //простите, что не написал эти две функции через шаблоны, просто спать хотелось
- void debug(vector<int> &b)
- {
- for(auto i : b)
- cout << i << ' ';
- cout << '\n';
- }
- int main(){
- int m = FastIntInput(), n = FastIntInput();
- vector<int> a = {-1}, b = {-1};
- do(_, m)
- a.push_back(FastIntInput());
- do(_, n)
- b.push_back(FastIntInput());
- multimap<int, int> b_izn, a_izn;
- do(_, m)
- a_izn.insert({a[_], _});
- do(_, n)
- b_izn.insert({b[_], _});
- sort(a.begin(), a.end());
- sort(b.begin(), b.end());
- int l = 0, r = min(m, n / 2) + 1;
- while(r - l > 1)
- {
- int mid = (r + l) / 2;
- bool povozka = true; // показывает, можно ли составить повозку
- set<int> a_copy = {-1};
- do(i, m){
- a_copy.insert(a[i]);
- }
- do(i, mid){
- int one = b[i];
- int two = b[n - mid + i];
- bool ok = false;
- int deer = *lower_bound(a.begin(), a.end(), one);
- if(deer > one && deer < two){
- ok = true;
- a_copy.erase(deer);
- break;
- }
- if(!ok)
- povozka = false;
- }
- //debug(a_copy);
- if(povozka)
- l = mid;
- else
- r = mid;
- }
- int mid = (r + l) / 2;
- cout << mid << '\n';
- multiset<int> a_copy = {-1};
- do(i, m){
- a_copy.insert(a[i]);
- }
- do(i, mid){
- int one = b[i];
- int two = b[n - mid + i];
- int deer = *(a_copy.lower_bound(one));
- a_copy.erase(a_copy.find(deer));
- int first = (*b_izn.find(one)).second;
- int second = (*b_izn.find(two)).second;
- int dear_izn = (*a_izn.find(deer)).second;
- cout << dear_izn << ' ' << first << ' ' << second << '\n';
- a_izn.erase(a_izn.find(deer));
- b_izn.erase(b_izn.find(two));
- b_izn.erase(b_izn.find(one));
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement