Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <iomanip>
- #include <cstdlib>
- #include <algorithm>
- #include <vector>
- #include <queue>
- #include <stack>
- #include <climits>
- #include <string>
- #include <set>
- #include <cmath>
- #include <map>
- #include <unordered_map>
- #include <numeric>
- #include <random>
- #include <memory>
- #include <chrono>
- #include <iterator>
- #include <functional>
- #include <unordered_set>
- #include <cassert>
- #include <cstring>
- #ifdef LOCAL
- #include "debug.h"
- #else
- #define debug(x...)
- #endif
- //#pragma GCC optimize("Ofast")
- //#define int ll
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- typedef pair < int, int > pii;
- typedef pair < ll, ll > pll;
- #define sz(x) int((x).size())
- #ifndef LOCAL
- mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- #else
- mt19937 rng(228);
- #endif
- const int N = 1e5 + 7;
- const int inf = INT_MAX / 2;
- const ll INF = LLONG_MAX / 3;
- const int MOD = 1e9 + 7;
- const double eps = 1e-6;
- const string cars[] = {"๐", "๐", "๐"};
- signed main() {
- #ifdef LOCAL
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- cout << fixed << setprecision(4);
- ios::sync_with_stdio(false);
- cin.tie();
- cout.tie();
- int n, k;
- cin >> n >> k;
- n *= 2;
- vector < pii > a(n);
- for (int i = 0; i < n; i++) {
- cin >> a[i].first;
- a[i].second = i + 1;
- }
- sort(a.begin(), a.end());
- vector < int > b;
- int m = 0;
- for (int i = 0; i < n; i++) {
- if (i % 2) {
- m += a[i].first;
- if (i + 1 < n) {
- b.push_back(a[i + 1].first - a[i].first);
- }
- }
- else {
- m -= a[i].first;
- }
- }
- if (k - m < 0 || k > a.back().first - a.front().first) {
- return cout << "No", 0;
- }
- k -= m;
- if (k == 0) {
- cout << "Yes\n";
- for (int i = 0; i + 1 < n; i += 2) {
- cout << a[i].second << " " << a[i + 1].second << "\n";
- }
- return 0;
- }
- debug(b);
- vector < int > dp(3e4 + 7);
- dp[0] = 1;
- for (int x : b) {
- for (int i = sz(dp) - 1; i >= 0; i--) {
- if (i + x < N && dp[i]) {
- if (!dp[i + x]) {
- dp[i + x] = x;
- }
- }
- }
- }
- debug(dp);
- if (!dp[k]) {
- return cout << "No", 0;
- }
- else {
- cout << "Yes\n";
- }
- multiset < int > s;
- for (int i = k; i; i -= dp[i]) {
- s.insert(dp[i]);
- }
- debug(s);
- int l = 1;
- for (int i = 2; i < n; i += 2) {
- int t = a[i].first - a[i - 1].first;
- if (s.find(t) != s.end()) {
- s.erase(s.find(t));
- cout << a[i - 1].second << " " << a[i].second << endl;
- }
- else {
- cout << l << " " << a[i - 1].second << endl;
- l = a[i].second;
- }
- }
- if (l != a[n - 2].second) {
- cout << l << " " << a.back().second;
- }
- else {
- cout << a[n - 2].second << " " << a.back().second;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement