3444 | 2023. 02. 27 22:06:46 | norbertvida | Találkozás | cpp17 | Időlimit túllépés 52/55 | 280ms | 7944 KiB |
#include <bits/stdc++.h>
using namespace std;
struct ip {
int mikor;
bool jott;
};
int main() {
iostream::sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
int fel = (N >> 1) + (N & 1);
vector<ip> idopontok;
for(int i = 0, t; i < N; i++) {
cin >> t;
idopontok.push_back({ t, true });
cin >> t;
idopontok.push_back({ t, false });
}
sort(idopontok.begin(), idopontok.end(), [](const ip &a, const ip &b) -> bool {
return a.mikor == b.mikor ? a.jott : a.mikor < b.mikor;
});
int kezd = 0, veg = 0, hossz = 0, jelen = 0, u = 0, v = -1, opt_kezd = -1, opt_veg = -1, opt_hossz = 1e9;
while(v < 2 * N) {
while(jelen < fel && v < 2 * N) {
v++;
if(idopontok[v].jott) jelen++;
}
if(v == 2 * N) break;
while(idopontok[u].jott && u < v) u++;
kezd = idopontok[u].mikor;
veg = idopontok[v].mikor;
hossz = veg - kezd;
if(hossz < opt_hossz) {
opt_hossz = hossz;
opt_kezd = kezd;
opt_veg = veg;
}
u++;
jelen--;
}
cout << opt_hossz + 1 << "\n" << opt_kezd << " " << opt_veg << "\n";
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 52/55 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1828 KiB | |||
2 | Elfogadva | 0/0 | 46ms | 6252 KiB | |||
3 | Elfogadva | 2/2 | 3ms | 2104 KiB | |||
4 | Elfogadva | 2/2 | 3ms | 2228 KiB | |||
5 | Elfogadva | 2/2 | 3ms | 2464 KiB | |||
6 | Elfogadva | 2/2 | 3ms | 2536 KiB | |||
7 | Elfogadva | 2/2 | 3ms | 2672 KiB | |||
8 | Elfogadva | 3/3 | 3ms | 2872 KiB | |||
9 | Elfogadva | 3/3 | 3ms | 3096 KiB | |||
10 | Elfogadva | 3/3 | 3ms | 3076 KiB | |||
11 | Elfogadva | 3/3 | 4ms | 3660 KiB | |||
12 | Elfogadva | 3/3 | 6ms | 3840 KiB | |||
13 | Elfogadva | 3/3 | 6ms | 3968 KiB | |||
14 | Elfogadva | 3/3 | 9ms | 4872 KiB | |||
15 | Elfogadva | 3/3 | 8ms | 5168 KiB | |||
16 | Elfogadva | 3/3 | 8ms | 5020 KiB | |||
17 | Elfogadva | 3/3 | 8ms | 5020 KiB | |||
18 | Elfogadva | 3/3 | 14ms | 5148 KiB | |||
19 | Elfogadva | 3/3 | 35ms | 7900 KiB | |||
20 | Időlimit túllépés | 0/3 | 280ms | 5212 KiB | |||
21 | Elfogadva | 3/3 | 46ms | 7944 KiB | |||
22 | Elfogadva | 3/3 | 46ms | 7896 KiB |