Raslboyy

414v1

Nov 12th, 2019
183
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.61 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 st = 0;
  31.     int end = 1;
  32.     int cur_d = 0;
  33.     int count = 0;
  34.     vector<bool> used(n_elf);
  35.     while (st < n_elf && end < n_elf && cur_d < n_deer) {
  36.         if (!used[st] && elf[st].x < deer[cur_d].x && deer[cur_d].x < elf[end].x) {
  37.             last_res[count][0] = deer[cur_d].y;
  38.             last_res[count][1] = elf[st].y;
  39.             last_res[count][2] = elf[end].y;
  40.             count++;
  41.             used[end] = 1;
  42.             st++, end++;
  43.             cur_d++;
  44.         }
  45.         else if (deer[cur_d].x >= elf[end].x)
  46.             end++;
  47.         else if (elf[st].x >= deer[cur_d].x)
  48.             cur_d++;
  49.         else if (used[st])
  50.             st++;
  51.         /*else if (elf[st].x >= deer[cur_d].x)
  52.         st++;
  53.         else if (deer[cur_d].x >= elf[end].x)
  54.         end++;*/
  55.     }
  56.     /*while (st < n_elf) {
  57.         if (elf[st].x < deer[cur_d].x && deer[cur_d].x < elf[end].x) {
  58.             last_res[count][0] = deer[cur_d].y;
  59.             last_res[count][1] = elf[st].y;
  60.             last_res[count][2] = elf[end].y;
  61.             count++;
  62.             st++, end++;
  63.             cur_d++;
  64.             used[end] = 1;
  65.         }
  66.         else {
  67.             st++;
  68.         }
  69.     }*/
  70.     return count >= len;
  71. }
  72.  
  73. int main() {
  74.     /*ifstream cin("in.txt");
  75.     ofstream cout("out.txt");
  76.     auto start_time = chrono::high_resolution_clock::now();*/
  77.  
  78.     ios::sync_with_stdio(false);
  79.     cin.tie(0);
  80.     cout.tie(0);
  81.  
  82.     cin >> n_deer >> n_elf;
  83.     deer.assign(n_deer, pi());
  84.     elf.assign(n_elf, pi());
  85.     last_res.assign(n_deer, vector<int>(3));
  86.     for (int i = 0; i < n_deer; i++) {
  87.         cin >> deer[i].x;
  88.         deer[i].y = i + 1;
  89.     }
  90.     for (int i = 0; i < n_elf; i++) {
  91.         cin >> elf[i].x;
  92.         elf[i].y = i + 1;
  93.     }
  94.     sort(all(deer), [](pi a, pi b) {
  95.         return a.x < b.x;
  96.     });
  97.     sort(all(elf), [](pi a, pi b) {
  98.         return a.x < b.x;
  99.     });
  100.    
  101.     int l = 0, r = n_deer + 1;
  102.     while (l + 1 < r) {
  103.         int mid = (l + r) / 2;
  104.         if (check(mid))
  105.             l = mid;
  106.         else
  107.             r = mid;
  108.     }
  109.     cout << l << "\n";
  110.     for (int i = 0; i < l; i++) {
  111.         for (int j = 0; j < 3; j++)
  112.             cout << last_res[i][j] << " ";
  113.         cout << "\n";
  114.     }
  115.    
  116.     /*auto end_time = chrono::high_resolution_clock::now();
  117.     chrono::duration<double> duration = end_time - start_time;
  118.     cout << duration.count() << "\n";
  119.     cin.close();
  120.     cout.close();*/
  121.     return 0;
  122. }
Advertisement
Add Comment
Please, Sign In to add comment