5733 | 2023. 09. 10 17:37:58 | kukkerman | Legmesszebbi rossz sorrendű (35 pont) | cpp14 | Elfogadva 35/35 | 54ms | 8048 KiB |
#include <iostream>
#include <vector>
std::vector<int> beolvas(std::istream &in) {
size_t n;
in >> n;
std::vector<int> v(n);
for (auto i = 0u; i < n; i++) {
in >> v[i];
}
return v;
}
size_t merge_sort(size_t kezd, size_t veg, std::vector<size_t> &honnan, std::vector<size_t> &hova, const std::vector<int> &v) {
size_t max_tav = 0u;
if (veg - kezd > 1) {
const auto kozep = kezd + (veg - kezd) / 2;
const auto bal_max_tav = merge_sort(kezd, kozep, hova, honnan, v);
const auto jobb_max_tav = merge_sort(kozep, veg, hova, honnan, v);
max_tav = std::max(bal_max_tav, jobb_max_tav);
size_t bal = kezd;
size_t jobb = kozep;
size_t cel = kezd;
size_t jobb_max_index = 0;
while (bal < kozep || jobb < veg) {
if (bal < kozep && (jobb == veg || v[honnan[bal]] <= v[honnan[jobb]])) {
if (jobb > kozep && max_tav < jobb_max_index - honnan[bal]) {
max_tav = jobb_max_index - honnan[bal];
}
hova[cel++] = honnan[bal++];
} else {
jobb_max_index = std::max(jobb_max_index, honnan[jobb]);
hova[cel++] = honnan[jobb++];
}
}
}
return max_tav;
}
void feldolgoz(const std::vector<int> &v) {
const auto n = v.size();
std::vector<size_t> honnan(n), hova(n);
for (auto i = 0u; i < n; i++) {
honnan[i] = hova[i] = i;
}
const auto max_tav = merge_sort(0, n, honnan, hova, v);
if (max_tav > 0) {
for (auto i = 0u; i < n; i++) {
if (v[i] > v[i + max_tav]) {
std::cout << i + 1 << ' ' << i + 1 + max_tav;
break;
}
}
} else {
std::cout << -1;
}
std::cout << std::endl;
}
int main() {
const auto v = beolvas(std::cin);
feldolgoz(v);
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 35/35 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1812 KiB | |||
2 | Elfogadva | 0/0 | 54ms | 6008 KiB | |||
3 | Elfogadva | 1/1 | 3ms | 2268 KiB | |||
4 | Elfogadva | 1/1 | 3ms | 2360 KiB | |||
5 | Elfogadva | 1/1 | 3ms | 2528 KiB | |||
6 | Elfogadva | 1/1 | 2ms | 2612 KiB | |||
7 | Elfogadva | 1/1 | 2ms | 2612 KiB | |||
8 | Elfogadva | 1/1 | 3ms | 2780 KiB | |||
9 | Elfogadva | 1/1 | 3ms | 3084 KiB | |||
10 | Elfogadva | 1/1 | 4ms | 3208 KiB | |||
11 | Elfogadva | 1/1 | 4ms | 3184 KiB | |||
12 | Elfogadva | 2/2 | 20ms | 4456 KiB | |||
13 | Elfogadva | 2/2 | 24ms | 4976 KiB | |||
14 | Elfogadva | 2/2 | 25ms | 5060 KiB | |||
15 | Elfogadva | 2/2 | 16ms | 4476 KiB | |||
16 | Elfogadva | 2/2 | 26ms | 5588 KiB | |||
17 | Elfogadva | 2/2 | 39ms | 6192 KiB | |||
18 | Elfogadva | 2/2 | 43ms | 6716 KiB | |||
19 | Elfogadva | 2/2 | 48ms | 7116 KiB | |||
20 | Elfogadva | 2/2 | 50ms | 7152 KiB | |||
21 | Elfogadva | 2/2 | 54ms | 7672 KiB | |||
22 | Elfogadva | 2/2 | 54ms | 7944 KiB | |||
23 | Elfogadva | 2/2 | 39ms | 8048 KiB | |||
24 | Elfogadva | 2/2 | 41ms | 7976 KiB |