// UUID: 6880f8ea-3ec5-44ea-ba4c-08e30d5f5101
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Etel {
int id;
int szav;
};
bool hasonlit(const Etel& a, const Etel& b) {
return a.szav < b.szav;
}
vector<Etel> negyesek_alap;
vector<Etel> otosok_alap;
vector<pair<int, int>> vegso_parok;
bool check(int K, bool mentes) {
vector<Etel> pool_4;
vector<Etel> pool_5;
int idx_4 = negyesek_alap.size() - 1;
int idx_5 = otosok_alap.size() - 1;
if (mentes) vegso_parok.clear();
for (int nap = K; nap >= 1; --nap) {
while (idx_4 >= 0 && negyesek_alap[idx_4].szav >= nap) {
pool_4.push_back(negyesek_alap[idx_4]);
idx_4--;
}
while (idx_5 >= 0 && otosok_alap[idx_5].szav >= nap) {
pool_5.push_back(otosok_alap[idx_5]);
idx_5--;
}
if (!pool_4.empty() && !pool_5.empty()) {
if (mentes) {
vegso_parok.push_back({pool_4.back().id, pool_5.back().id});
}
pool_4.pop_back();
pool_5.pop_back();
}
else if (pool_5.size() >= 2) {
if (mentes) {
int e1 = pool_5.back().id;
pool_5.pop_back();
int e2 = pool_5.back().id;
pool_5.pop_back();
vegso_parok.push_back({e1, e2});
} else {
pool_5.pop_back();
pool_5.pop_back();
}
}
else {
return false;
}
}
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
if (!(cin >> N)) return 0;
for (int i = 1; i <= N; ++i) {
int s, m;
cin >> s >> m;
if (m == 4) {
negyesek_alap.push_back({i, s});
} else if (m >= 5) {
otosok_alap.push_back({i, s});
}
}
sort(negyesek_alap.begin(), negyesek_alap.end(), hasonlit);
sort(otosok_alap.begin(), otosok_alap.end(), hasonlit);
int bal = 0;
int jobb = N / 2;
int megoldas = 0;
while (bal <= jobb) {
int kozep = bal + (jobb - bal) / 2;
if (check(kozep, false)) {
megoldas = kozep;
bal = kozep + 1;
} else {
jobb = kozep - 1;
}
}
cout << megoldas << "\n";
if (megoldas > 0) {
check(megoldas, true);
for (int i = vegso_parok.size() - 1; i >= 0; i--) {
cout << vegso_parok[i].first << " " << vegso_parok[i].second << "\n";
}
}
return 0;
}| Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
|---|---|---|---|---|---|---|---|
| subtask1 | 0/0 | ||||||
| 1 | Elfogadva | 1ms | 316 KiB | ||||
| subtask2 | 10/10 | ||||||
| 2 | Elfogadva | 1ms | 316 KiB | ||||
| 3 | Elfogadva | 1ms | 316 KiB | ||||
| 4 | Elfogadva | 1ms | 316 KiB | ||||
| 5 | Elfogadva | 1ms | 316 KiB | ||||
| 6 | Elfogadva | 1ms | 316 KiB | ||||
| 7 | Elfogadva | 1ms | 316 KiB | ||||
| 8 | Elfogadva | 1ms | 316 KiB | ||||
| 9 | Elfogadva | 1ms | 508 KiB | ||||
| 10 | Elfogadva | 1ms | 316 KiB | ||||
| 11 | Elfogadva | 1ms | 316 KiB | ||||
| subtask3 | 20/20 | ||||||
| 12 | Elfogadva | 1ms | 316 KiB | ||||
| 13 | Elfogadva | 1ms | 316 KiB | ||||
| 14 | Elfogadva | 1ms | 316 KiB | ||||
| 15 | Elfogadva | 1ms | 316 KiB | ||||
| 16 | Elfogadva | 1ms | 540 KiB | ||||
| 17 | Elfogadva | 1ms | 316 KiB | ||||
| 18 | Elfogadva | 1ms | 316 KiB | ||||
| 19 | Elfogadva | 1ms | 508 KiB | ||||
| 20 | Elfogadva | 1ms | 316 KiB | ||||
| 21 | Elfogadva | 1ms | 316 KiB | ||||
| 22 | Elfogadva | 1ms | 316 KiB | ||||
| 23 | Elfogadva | 1ms | 376 KiB | ||||
| 24 | Elfogadva | 2ms | 316 KiB | ||||
| 25 | Elfogadva | 2ms | 316 KiB | ||||
| 26 | Elfogadva | 1ms | 316 KiB | ||||
| 27 | Elfogadva | 1ms | 316 KiB | ||||
| 28 | Elfogadva | 1ms | 376 KiB | ||||
| 29 | Elfogadva | 1ms | 316 KiB | ||||
| 30 | Elfogadva | 2ms | 316 KiB | ||||
| 31 | Elfogadva | 1ms | 500 KiB | ||||
| subtask4 | 15/15 | ||||||
| 32 | Elfogadva | 1ms | 316 KiB | ||||
| 33 | Elfogadva | 1ms | 316 KiB | ||||
| 34 | Elfogadva | 1ms | 316 KiB | ||||
| 35 | Elfogadva | 1ms | 316 KiB | ||||
| 36 | Elfogadva | 1ms | 316 KiB | ||||
| 37 | Elfogadva | 1ms | 316 KiB | ||||
| 38 | Elfogadva | 1ms | 316 KiB | ||||
| 39 | Elfogadva | 1ms | 316 KiB | ||||
| 40 | Elfogadva | 1ms | 316 KiB | ||||
| 41 | Elfogadva | 1ms | 316 KiB | ||||
| 42 | Elfogadva | 1ms | 316 KiB | ||||
| 43 | Elfogadva | 1ms | 316 KiB | ||||
| 44 | Elfogadva | 1ms | 400 KiB | ||||
| 45 | Elfogadva | 1ms | 316 KiB | ||||
| 46 | Elfogadva | 1ms | 508 KiB | ||||
| subtask5 | 15/15 | ||||||
| 47 | Elfogadva | 1ms | 316 KiB | ||||
| 48 | Elfogadva | 1ms | 316 KiB | ||||
| 49 | Elfogadva | 1ms | 316 KiB | ||||
| 50 | Elfogadva | 1ms | 316 KiB | ||||
| 51 | Elfogadva | 1ms | 316 KiB | ||||
| 52 | Elfogadva | 1ms | 316 KiB | ||||
| 53 | Elfogadva | 1ms | 348 KiB | ||||
| 54 | Elfogadva | 1ms | 508 KiB | ||||
| 55 | Elfogadva | 1ms | 316 KiB | ||||
| 56 | Elfogadva | 1ms | 316 KiB | ||||
| 57 | Elfogadva | 1ms | 316 KiB | ||||
| 58 | Elfogadva | 1ms | 368 KiB | ||||
| 59 | Elfogadva | 1ms | 512 KiB | ||||
| 60 | Elfogadva | 1ms | 512 KiB | ||||
| 61 | Elfogadva | 1ms | 316 KiB | ||||
| subtask6 | 15/15 | ||||||
| 62 | Elfogadva | 1ms | 316 KiB | ||||
| 63 | Elfogadva | 2ms | 316 KiB | ||||
| 64 | Elfogadva | 2ms | 316 KiB | ||||
| 65 | Elfogadva | 1ms | 444 KiB | ||||
| 66 | Elfogadva | 2ms | 328 KiB | ||||
| 67 | Elfogadva | 1ms | 316 KiB | ||||
| 68 | Elfogadva | 1ms | 316 KiB | ||||
| 69 | Elfogadva | 1ms | 368 KiB | ||||
| 70 | Elfogadva | 1ms | 500 KiB | ||||
| 71 | Elfogadva | 1ms | 316 KiB | ||||
| 72 | Elfogadva | 1ms | 316 KiB | ||||
| 73 | Elfogadva | 2ms | 316 KiB | ||||
| 74 | Elfogadva | 1ms | 316 KiB | ||||
| 75 | Elfogadva | 1ms | 560 KiB | ||||
| 76 | Elfogadva | 1ms | 316 KiB | ||||