7747 2024. 01. 11 05:06:12 TuruTamas Találkozás cpp17 Elfogadva 55/55 200ms 7636 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";
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 55/55
1 Elfogadva 0/0 3ms 1892 KiB
2 Elfogadva 0/0 200ms 5228 KiB
3 Elfogadva 2/2 3ms 2436 KiB
4 Elfogadva 2/2 3ms 2392 KiB
5 Elfogadva 2/2 3ms 2604 KiB
6 Elfogadva 2/2 3ms 2820 KiB
7 Elfogadva 2/2 3ms 3020 KiB
8 Elfogadva 3/3 3ms 3228 KiB
9 Elfogadva 3/3 3ms 3312 KiB
10 Elfogadva 3/3 3ms 3444 KiB
11 Elfogadva 3/3 13ms 3800 KiB
12 Elfogadva 3/3 17ms 3856 KiB
13 Elfogadva 3/3 18ms 3928 KiB
14 Elfogadva 3/3 35ms 4168 KiB
15 Elfogadva 3/3 35ms 4168 KiB
16 Elfogadva 3/3 32ms 4136 KiB
17 Elfogadva 3/3 34ms 4132 KiB
18 Elfogadva 3/3 63ms 4708 KiB
19 Elfogadva 3/3 34ms 7124 KiB
20 Elfogadva 3/3 75ms 7080 KiB
21 Elfogadva 3/3 200ms 7340 KiB
22 Elfogadva 3/3 199ms 7636 KiB