77472024-01-11 05:06:12TuruTamasTalálkozáscpp17Accepted 55/55200ms7636 KiB
#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
ifstream in_file("minta/be2.txt");
#define input in_file
#define INTHENAMEOFGOD
#else
#define input cin
#define INTHENAMEOFGOD \
    ios::sync_with_stdio(0); \
    cin.tie(0); \
    cout.tie(0);
#endif
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef pair<ll, ll> pii;

ll N, a, b;
vector<ll> lsort, rsort;

inline ll talalkaszam(ll bal, ll jobb) {
    ll baltol_jobbra = rsort.end() - lower_bound(rsort.begin(), rsort.end(), bal);
    ll jobbtol_balra = upper_bound(lsort.begin(), lsort.end(), jobb) - lsort.begin();

    return baltol_jobbra + jobbtol_balra - N;
}

int main() {
    INTHENAMEOFGOD
    input >> N;
    lsort.reserve(N);
    rsort.reserve(N);
    for (ll n = 0; n < N; n++) {
        input >> a >> b;
        
        lsort.push_back(a);
        rsort.push_back(b);
    }
    sort(lsort.begin(), lsort.end());
    sort(rsort.begin(), rsort.end());

    ll min_tszam = LLONG_MAX, min_hossz = LLONG_MAX, min_kibal, min_kijobb;
    
    for (ll kibaljobb : lsort) {
        if (talalkaszam(kibaljobb, kibaljobb) == N/2+N%2) {
            cout << 1 << "\n" << kibaljobb << " " << kibaljobb << "\n";
            exit(0);
        }
    }

    for (auto kibal : rsort) {
        ll l = kibal;
        ll r = 100000;
        ll kijobb;
        while (l <= r) {
            kijobb = (l+r)/2;
            if (l == r) {
                break;
            }
            ll tszam = talalkaszam(kibal, kijobb);
            if (tszam < N/2+N%2) {
                l = kijobb+1;
            }
            else if (tszam > N/2+N%2) {
                r = kijobb-1;
            }
            else if (tszam == N/2+N%2) {
                r = kijobb;
            }
        }
        ll tszam = talalkaszam(kibal, kijobb);
        if (
            tszam >= N/2+N%2
            && (tszam < min_tszam || (tszam == min_tszam && kijobb-kibal < min_hossz))
            ) {
            min_hossz = kijobb-kibal;
            min_tszam = tszam;
            min_kibal = kibal;
            min_kijobb = kijobb;
        }
    }
    cout << min_kijobb-min_kibal+1 << "\n" << min_kibal << " " << min_kijobb << "\n";
}
SubtaskSumTestVerdictTimeMemory
base55/55
1Accepted0/03ms1892 KiB
2Accepted0/0200ms5228 KiB
3Accepted2/23ms2436 KiB
4Accepted2/23ms2392 KiB
5Accepted2/23ms2604 KiB
6Accepted2/23ms2820 KiB
7Accepted2/23ms3020 KiB
8Accepted3/33ms3228 KiB
9Accepted3/33ms3312 KiB
10Accepted3/33ms3444 KiB
11Accepted3/313ms3800 KiB
12Accepted3/317ms3856 KiB
13Accepted3/318ms3928 KiB
14Accepted3/335ms4168 KiB
15Accepted3/335ms4168 KiB
16Accepted3/332ms4136 KiB
17Accepted3/334ms4132 KiB
18Accepted3/363ms4708 KiB
19Accepted3/334ms7124 KiB
20Accepted3/375ms7080 KiB
21Accepted3/3200ms7340 KiB
22Accepted3/3199ms7636 KiB