Advertisement
aayyk

Untitled

Dec 4th, 2019
173
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.12 KB | None | 0 0
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <cstdlib>
  4. #include <algorithm>
  5. #include <vector>
  6. #include <queue>
  7. #include <stack>
  8. #include <climits>
  9. #include <string>
  10. #include <set>
  11. #include <cmath>
  12. #include <map>
  13. #include <unordered_map>
  14. #include <numeric>
  15. #include <random>
  16. #include <memory>
  17. #include <chrono>
  18. #include <iterator>
  19. #include <functional>
  20. #include <unordered_set>
  21. #include <cassert>
  22. #include <cstring>
  23. #ifdef LOCAL
  24. #include "debug.h"
  25. #else
  26. #define debug(x...)
  27. #endif
  28. //#pragma GCC optimize("Ofast")
  29. //#define int ll
  30.  
  31.  
  32.  
  33. using namespace std;
  34. typedef long long ll;
  35. typedef long double ld;
  36. typedef pair < int, int > pii;
  37. typedef pair < ll, ll > pll;
  38. #define sz(x) int((x).size())
  39.  
  40. #ifndef LOCAL
  41. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  42. #else
  43. mt19937 rng(228);
  44. #endif
  45.  
  46. const int N = 1e5 + 7;
  47. const int inf = INT_MAX / 2;
  48. const ll INF = LLONG_MAX / 3;
  49. const int MOD = 1e9 + 7;
  50. const double eps = 1e-6;
  51. const string cars[] = {"๐Ÿš—", "๐Ÿš•", "๐Ÿš™"};
  52.  
  53. signed main() {
  54. #ifdef LOCAL
  55.     freopen("input.txt", "r", stdin);
  56.     freopen("output.txt", "w", stdout);
  57. #endif
  58.     cout << fixed << setprecision(4);
  59.     ios::sync_with_stdio(false);
  60.     cin.tie();
  61.     cout.tie();
  62.  
  63.     int n, k;
  64.     cin >> n >> k;
  65.     n *= 2;
  66.  
  67.     vector < pii > a(n);
  68.     for (int i = 0; i < n; i++) {
  69.         cin >> a[i].first;
  70.         a[i].second = i + 1;
  71.     }
  72.  
  73.     sort(a.begin(), a.end());
  74.     vector < int > b;
  75.     int m = 0;
  76.  
  77.     for (int i = 0; i < n; i++) {
  78.         if (i % 2) {
  79.             m += a[i].first;
  80.  
  81.             if (i + 1 < n) {
  82.                 b.push_back(a[i + 1].first - a[i].first);
  83.             }
  84.         }
  85.         else {
  86.             m -= a[i].first;
  87.         }
  88.     }
  89.  
  90.     if (k - m < 0 || k > a.back().first - a.front().first) {
  91.         return cout << "No", 0;
  92.     }
  93.     k -= m;
  94.  
  95.     if (k == 0) {
  96.         cout << "Yes\n";
  97.         for (int i = 0; i + 1 < n; i += 2) {
  98.             cout << a[i].second << " " << a[i + 1].second << "\n";
  99.         }
  100.         return 0;
  101.     }
  102.  
  103.     debug(b);
  104.  
  105.     vector < int > dp(3e4 + 7);
  106.  
  107.     dp[0] = 1;
  108.     for (int x : b) {
  109.         for (int i = sz(dp) - 1; i >= 0; i--) {
  110.             if (i + x < N && dp[i]) {
  111.                 if (!dp[i + x]) {
  112.                     dp[i + x] = x;
  113.                 }
  114.             }
  115.         }
  116.     }
  117.     debug(dp);
  118.  
  119.     if (!dp[k]) {
  120.         return cout << "No", 0;
  121.     }
  122.     else {
  123.         cout << "Yes\n";
  124.     }
  125.  
  126.     multiset < int > s;
  127.     for (int i = k; i; i -= dp[i]) {
  128.         s.insert(dp[i]);
  129.     }
  130.     debug(s);
  131.  
  132.     int l = 1;
  133.     for (int i = 2; i < n; i += 2) {
  134.         int t = a[i].first - a[i - 1].first;
  135.         if (s.find(t) != s.end()) {
  136.             s.erase(s.find(t));
  137.             cout << a[i - 1].second << " " << a[i].second << endl;
  138.         }
  139.         else {
  140.             cout << l << " " << a[i - 1].second << endl;
  141.             l = a[i].second;
  142.         }
  143.     }
  144.  
  145.     if (l != a[n - 2].second) {
  146.         cout << l << " " << a.back().second;
  147.     }
  148.     else {
  149.         cout << a[n - 2].second << " " << a.back().second;
  150.     }
  151.  
  152.     return 0;
  153. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement