77462024-01-11 05:03:23TuruTamasTalálkozáscpp17Time limit exceeded 49/55204ms10112 KiB
#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
ifstream in_file("minta/be1.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;
vector<pii> beszok;

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;
    for (ll n = 0; n < N; n++) {
        input >> a >> b;
        
        lsort.push_back(a);
        rsort.push_back(b);
        beszok.emplace_back(a, 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
base49/55
1Accepted0/03ms1892 KiB
2Time limit exceeded0/0204ms8640 KiB
3Accepted2/23ms2440 KiB
4Accepted2/23ms2572 KiB
5Accepted2/23ms2804 KiB
6Accepted2/23ms2736 KiB
7Accepted2/23ms2940 KiB
8Accepted3/33ms3000 KiB
9Accepted3/33ms3004 KiB
10Accepted3/33ms3268 KiB
11Accepted3/313ms4004 KiB
12Accepted3/318ms4604 KiB
13Accepted3/318ms4464 KiB
14Accepted3/335ms5080 KiB
15Accepted3/335ms4976 KiB
16Accepted3/334ms4976 KiB
17Accepted3/335ms5248 KiB
18Accepted3/364ms5316 KiB
19Accepted3/337ms9920 KiB
20Accepted3/376ms10080 KiB
21Time limit exceeded0/3204ms10112 KiB
22Time limit exceeded0/3203ms10088 KiB