Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- //#include <chrono>
- //#include <fstream>
- //#include <bits/stdc++.h>
- #include <vector>
- #include <algorithm>
- #define mp make_pair
- #define pb push_back
- #define eb emplace_back
- #define x first
- #define y second
- #define sz(x) (int)x.size()
- #define all(x) begin(x), end(x)
- #define rall(x) rbegin(x), rend(x)
- using namespace std;
- typedef unsigned long long ull;
- typedef long long ll;
- typedef long double ld;
- typedef pair<int, int> pi;
- typedef pair<ll, ll> pl;
- int n_deer, n_elf;
- vector<pi> deer, elf;
- vector<vector<int>> last_res;
- bool check(int len) {
- int st = 0;
- int end = 1;
- int cur_d = 0;
- int count = 0;
- vector<bool> used(n_elf);
- while (st < n_elf && end < n_elf && cur_d < n_deer) {
- if (!used[st] && elf[st].x < deer[cur_d].x && deer[cur_d].x < elf[end].x) {
- last_res[count][0] = deer[cur_d].y;
- last_res[count][1] = elf[st].y;
- last_res[count][2] = elf[end].y;
- count++;
- used[end] = 1;
- st++, end++;
- cur_d++;
- }
- else if (deer[cur_d].x >= elf[end].x)
- end++;
- else if (elf[st].x >= deer[cur_d].x)
- cur_d++;
- else if (used[st])
- st++;
- /*else if (elf[st].x >= deer[cur_d].x)
- st++;
- else if (deer[cur_d].x >= elf[end].x)
- end++;*/
- }
- /*while (st < n_elf) {
- if (elf[st].x < deer[cur_d].x && deer[cur_d].x < elf[end].x) {
- last_res[count][0] = deer[cur_d].y;
- last_res[count][1] = elf[st].y;
- last_res[count][2] = elf[end].y;
- count++;
- st++, end++;
- cur_d++;
- used[end] = 1;
- }
- else {
- st++;
- }
- }*/
- return count >= len;
- }
- int main() {
- /*ifstream cin("in.txt");
- ofstream cout("out.txt");
- auto start_time = chrono::high_resolution_clock::now();*/
- ios::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- cin >> n_deer >> n_elf;
- deer.assign(n_deer, pi());
- elf.assign(n_elf, pi());
- last_res.assign(n_deer, vector<int>(3));
- for (int i = 0; i < n_deer; i++) {
- cin >> deer[i].x;
- deer[i].y = i + 1;
- }
- for (int i = 0; i < n_elf; i++) {
- cin >> elf[i].x;
- elf[i].y = i + 1;
- }
- sort(all(deer), [](pi a, pi b) {
- return a.x < b.x;
- });
- sort(all(elf), [](pi a, pi b) {
- return a.x < b.x;
- });
- int l = 0, r = n_deer + 1;
- while (l + 1 < r) {
- int mid = (l + r) / 2;
- if (check(mid))
- l = mid;
- else
- r = mid;
- }
- cout << l << "\n";
- for (int i = 0; i < l; i++) {
- for (int j = 0; j < 3; j++)
- cout << last_res[i][j] << " ";
- cout << "\n";
- }
- /*auto end_time = chrono::high_resolution_clock::now();
- chrono::duration<double> duration = end_time - start_time;
- cout << duration.count() << "\n";
- cin.close();
- cout.close();*/
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment