oj.uz

답안 #752912

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
752912 2023-06-04T09:01:44 Z I_love_Hoang_Yen 서열 (APIO23_sequence) C++17
7 / 100
 189 ms 31664 KB 
#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) {
    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 sub4(const vector<int>& a) {
    int n = SZ(a);
    vector<vector<int>> cnt(3, vector<int> (n, 0));
    for (int val = 0; val < 3; ++val) {
        for (int i = 0; i < n; ++i) {
            if (i) cnt[val][i] = cnt[val][i-1];
            cnt[val][i] += (val+1) == a[i];
        }
    }

    for (int l = 0; l < n; ++l) {
    }
}

int sequence(int n, std::vector<int> a) {
    if (is_sub_3(a)) return sub3(a);
    if (*max_element(a.begin(), a.end()) <= 3) return sub4(a);
    if (n <= 2000) return sub2(a);
    return 0;
}

Compilation message

sequence.cpp: In function 'int sub4(const std::vector<int>&)':
sequence.cpp:118:1: warning: no return statement in function returning non-void [-Wreturn-type]
  118 | }
      | ^

Subtask #1
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 1 ms 340 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 1 ms 340 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 157 ms 31600 KB Output is correct
3 Correct 189 ms 31664 KB Output is correct
4 Correct 37 ms 6096 KB Output is correct
5 Correct 173 ms 29144 KB Output is correct
6 Correct 146 ms 29192 KB Output is correct
7 Correct 40 ms 6100 KB Output is correct
8 Correct 48 ms 6104 KB Output is correct
9 Correct 38 ms 6088 KB Output is correct

Subtask #4
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 44 ms 6100 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 1 ms 340 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 1 ms 340 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -