#include "sequence.h"
#include <bits/stdc++.h>
#define SZ(s) ((int) ((s).size()))
using namespace std;
vector<int> medians(const vector<int> values) {
int n = SZ(values);
assert(n > 0);
if (n % 2 == 0) {
return {values[n/2 - 1], values[n / 2]};
} else {
return {values[n/2]};
}
}
int sub1(const vector<int>& a) {
int n = SZ(a);
int res = 0;
for (int l = 0; l < n; ++l) {
for (int r = l; r < n; ++r) {
vector<int> b(a.begin() + l, a.begin() + r + 1);
unordered_map<int, int> cnt;
for (int val : b) cnt[val] += 1;
sort(b.begin(), b.end());
auto meds = medians(b);
for (int med : meds) {
res = max(res, cnt[med]);
}
}
}
return res;
}
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
using namespace __gnu_pbds;
int sub2(const vector<int>& a) {
int n = SZ(a);
int res = 0;
for (int l = 0; l < n; ++l) {
unordered_map<int, int> cnt;
ordered_set values;
for (int r = l; r < n; ++r) {
cnt[a[r]]++;
values.insert(a[r]);
int k = SZ(values);
if (k % 2 == 0) {
res = max(res, cnt[*values.find_by_order(k / 2 - 1)]);
res = max(res, cnt[*values.find_by_order(k / 2)]);
} else {
res = max(res, cnt[*values.find_by_order(k / 2)]);
}
}
}
return res;
}
bool is_sub_3(const std::vector<int> a) {
auto mit = max_element(a.begin(), a.end());
return std::is_sorted(a.begin(), mit)
&& std::is_sorted(mit, a.end(), std::greater<int>());
}
int len(const std::pair<int,int>& p) {
return p.second - p.first + 1;
}
bool can_be_median(int cnt_less, int cnt_equal, int cnt_greater) {
if (cnt_equal >= cnt_greater) return true;
else return cnt_equal + cnt_less >= cnt_greater;
}
int sub3(const vector<int>& a) {
int n = SZ(a);
unordered_map<int, vector<pair<int,int>>> pos;
int l = 0;
while (l < n) {
int r = l;
while (r < n && a[l] == a[r]) ++r;
pos[a[l]].emplace_back(l, r-1);
l = r;
}
int res = 0;
for (const auto& [val, lrs] : pos) {
// only 1 segment
for (const auto& lr : lrs) res = max(res, len(lr));
// 2 segments
if (SZ(lrs) < 2) continue;
assert(SZ(lrs) == 2);
int cnt_equal = len(lrs[0]) + len(lrs[1]);
int cnt_greater = len({lrs[0].second + 1, lrs[1].first - 1});
int cnt_less = len({0, lrs[0].first - 1}) + len({lrs[1].second + 1, n-1});
if (can_be_median(cnt_less, cnt_equal, cnt_greater)) {
res = max(res, cnt_equal);
}
}
return res;
}
int sequence(int n, std::vector<int> a) {
if (is_sub_3(a)) return sub3(a);
if (n <= 2000) return sub2(a);
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
2 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
2 ms |
212 KB |
Output is correct |
12 |
Correct |
2 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
2 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
2 ms |
212 KB |
Output is correct |
12 |
Correct |
2 ms |
212 KB |
Output is correct |
13 |
Correct |
681 ms |
468 KB |
Output is correct |
14 |
Correct |
664 ms |
472 KB |
Output is correct |
15 |
Correct |
454 ms |
392 KB |
Output is correct |
16 |
Correct |
461 ms |
384 KB |
Output is correct |
17 |
Correct |
431 ms |
384 KB |
Output is correct |
18 |
Correct |
1 ms |
468 KB |
Output is correct |
19 |
Correct |
632 ms |
548 KB |
Output is correct |
20 |
Correct |
629 ms |
436 KB |
Output is correct |
21 |
Correct |
633 ms |
444 KB |
Output is correct |
22 |
Correct |
684 ms |
444 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
150 ms |
31656 KB |
Output is correct |
3 |
Correct |
178 ms |
31688 KB |
Output is correct |
4 |
Correct |
42 ms |
6100 KB |
Output is correct |
5 |
Correct |
171 ms |
29216 KB |
Output is correct |
6 |
Correct |
152 ms |
29144 KB |
Output is correct |
7 |
Correct |
41 ms |
6108 KB |
Output is correct |
8 |
Correct |
42 ms |
6092 KB |
Output is correct |
9 |
Correct |
41 ms |
6104 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Incorrect |
42 ms |
6088 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
52 ms |
6088 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
2 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
2 ms |
212 KB |
Output is correct |
12 |
Correct |
2 ms |
212 KB |
Output is correct |
13 |
Correct |
681 ms |
468 KB |
Output is correct |
14 |
Correct |
664 ms |
472 KB |
Output is correct |
15 |
Correct |
454 ms |
392 KB |
Output is correct |
16 |
Correct |
461 ms |
384 KB |
Output is correct |
17 |
Correct |
431 ms |
384 KB |
Output is correct |
18 |
Correct |
1 ms |
468 KB |
Output is correct |
19 |
Correct |
632 ms |
548 KB |
Output is correct |
20 |
Correct |
629 ms |
436 KB |
Output is correct |
21 |
Correct |
633 ms |
444 KB |
Output is correct |
22 |
Correct |
684 ms |
444 KB |
Output is correct |
23 |
Incorrect |
9 ms |
1236 KB |
Output isn't correct |
24 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
2 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
2 ms |
212 KB |
Output is correct |
12 |
Correct |
2 ms |
212 KB |
Output is correct |
13 |
Correct |
681 ms |
468 KB |
Output is correct |
14 |
Correct |
664 ms |
472 KB |
Output is correct |
15 |
Correct |
454 ms |
392 KB |
Output is correct |
16 |
Correct |
461 ms |
384 KB |
Output is correct |
17 |
Correct |
431 ms |
384 KB |
Output is correct |
18 |
Correct |
1 ms |
468 KB |
Output is correct |
19 |
Correct |
632 ms |
548 KB |
Output is correct |
20 |
Correct |
629 ms |
436 KB |
Output is correct |
21 |
Correct |
633 ms |
444 KB |
Output is correct |
22 |
Correct |
684 ms |
444 KB |
Output is correct |
23 |
Correct |
150 ms |
31656 KB |
Output is correct |
24 |
Correct |
178 ms |
31688 KB |
Output is correct |
25 |
Correct |
42 ms |
6100 KB |
Output is correct |
26 |
Correct |
171 ms |
29216 KB |
Output is correct |
27 |
Correct |
152 ms |
29144 KB |
Output is correct |
28 |
Correct |
41 ms |
6108 KB |
Output is correct |
29 |
Correct |
42 ms |
6092 KB |
Output is correct |
30 |
Correct |
41 ms |
6104 KB |
Output is correct |
31 |
Incorrect |
42 ms |
6088 KB |
Output isn't correct |
32 |
Halted |
0 ms |
0 KB |
- |