Raslboyy

414м2

Nov 12th, 2019
125
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.96 KB | None | 0 0
  1. #include <iostream>
  2. //#include <chrono>
  3. //#include <fstream>
  4. //#include <bits/stdc++.h>
  5. #include <vector>
  6. #include <algorithm>
  7.  
  8. #define mp make_pair
  9. #define pb push_back
  10. #define eb emplace_back
  11. #define x first
  12. #define y second
  13. #define sz(x) (int)x.size()
  14. #define all(x) begin(x), end(x)
  15. #define rall(x) rbegin(x), rend(x)
  16.  
  17. using namespace std;
  18.  
  19. typedef unsigned long long ull;
  20. typedef long long ll;
  21. typedef long double ld;
  22. typedef pair<int, int> pi;
  23. typedef pair<ll, ll> pl;
  24.  
  25. int n_deer, n_elf;
  26. vector<pi> deer, elf;
  27. vector<vector<int>> last_res;
  28.  
  29. bool check(int len) {
  30.     int i = 0;
  31.     for (int cur_d = 0; cur_d < n_deer && i < len; cur_d++) {
  32.         if (elf[i].x < deer[cur_d].x && deer[cur_d].x < elf[n_elf - len + cnt].x) {
  33.             last_res[i][0] = deer[cur_d].y;
  34.             last_res[i][1] = elf[i].y;
  35.             last_res[i][2] = elf[n_elf - len + cnt].y;
  36.             i++;
  37.         }
  38.            
  39.     }
  40.     return i >= len;
  41. }
  42.  
  43. int main() {
  44.     /*ifstream cin("in.txt");
  45.     ofstream cout("out.txt");
  46.     auto start_time = chrono::high_resolution_clock::now();*/
  47.  
  48.     ios::sync_with_stdio(false);
  49.     cin.tie(0);
  50.     cout.tie(0);
  51.  
  52.     cin >> n_deer >> n_elf;
  53.     deer.assign(n_deer, pi());
  54.     elf.assign(n_elf, pi());
  55.     last_res.assign(n_deer, vector<int>(3));
  56.     for (int i = 0; i < n_deer; i++) {
  57.         cin >> deer[i].x;
  58.         deer[i].y = i + 1;
  59.     }
  60.     for (int i = 0; i < n_elf; i++) {
  61.         cin >> elf[i].x;
  62.         elf[i].y = i + 1;
  63.     }
  64.     sort(all(deer), [](pi a, pi b) {
  65.         return a.x <= b.x;
  66.     });
  67.     sort(all(elf), [](pi a, pi b) {
  68.         return a.x <= b.x;
  69.     });
  70.    
  71.     int l = 0, r = min(n_deer, n_elf/2);
  72.     while (l + 1 < r) {
  73.         int mid = (l + r) / 2;
  74.         if (check(mid))
  75.             l = mid;
  76.         else
  77.             r = mid;
  78.     }
  79.     cout << l << "\n";
  80.     for (int i = 0; i < l; i++) {
  81.         for (int j = 0; j < 3; j++)
  82.             cout << last_res[i][j] << " ";
  83.         cout << "\n";
  84.     }
  85.    
  86.     /*auto end_time = chrono::high_resolution_clock::now();
  87.     chrono::duration<double> duration = end_time - start_time;
  88.     cout << duration.count() << "\n";
  89.     cin.close();
  90.     cout.close();*/
  91.     return 0;
  92. }
Add Comment
Please, Sign In to add comment