oj.uz

답안 #136299

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
136299 2019-07-25T05:57:34 Z imeimi2000 Meandian (CEOI06_meandian) C++17
100 / 100
 13 ms 444 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <functional>
#include "libmean.h"

using namespace std;
typedef long long llong;

int n;
int A[101];

int query(int a, int b, int c, int d) {
    static map<int, int> ret;
    vector<int> v;
    v.push_back(a);
    v.push_back(b);
    v.push_back(c);
    v.push_back(d);
    sort(v.begin(), v.end());
    int h = v[0] * 1000000 + v[1] * 10000 + v[2] * 100 + v[3];
    if (ret.count(h)) return ret[h];
    return ret[h] = Meandian(a, b, c, d);
}

template <class T>
vector<int> get_min_2(T cmp) {
    int a = 1, b = 2, c = 3, d = 4, v = query(1, 2, 3, 4);
    for (int i = 5; i <= n; ++i) {
        int e = i;
        swap(a, e);
        if (cmp(query(a, b, c, d), v)) v = query(a, b, c, d);
        else swap(a, e);
        swap(b, e);
        if (cmp(query(a, b, c, d), v)) v = query(a, b, c, d);
        else swap(b, e);
        swap(c, e);
        if (cmp(query(a, b, c, d), v)) v = query(a, b, c, d);
        else swap(c, e);
        swap(d, e);
        if (cmp(query(a, b, c, d), v)) v = query(a, b, c, d);
        else swap(d, e);
    }
    int e;
    for (e = 1; e <= n; ++e) {
        if (e == a) continue;
        if (e == b) continue;
        if (e == c) continue;
        if (e == d) continue;
        break;
    }
    if (query(a, b, c, e) == v);
    else if (query(a, b, e, d) == v) swap(c, d);
    else if (query(a, e, c, d) == v) swap(b, d);
    else swap(a, d);
    if (query(a, b, e, d) == query(a, e, c, d)) swap(a, c);
    else if (query(a, b, e, d) == query(e, b, c, d)) swap(b, c);
    return { a, b };
}

int S[101];
int main() {
    n = Init();
    for (int i = 1; i <= n; ++i) A[i] = -1;
    if (n > 4) {
        vector<int> min2 = get_min_2(less<int>());
        vector<int> max2 = get_min_2(greater<int>());
        vector<int> etc;
        int mn = min2[0], mx = max2[0];
        for (int i = 1; i <= n; ++i) {
            if (mn == i) continue;
            if (mx == i) continue;
            etc.push_back(i);
        }
        llong sum = 0;
        for (int i = 0; i < etc.size(); ++i) {
            int j = (i + 1) % etc.size();
            sum += S[i] = query(etc[i], etc[j], mn, mx);
        }
        for (int i = 0; i < etc.size(); ++i) {
            int l = (i + etc.size() - 1) % etc.size();
            int r = (i + 1) % etc.size();
            llong tsum = sum - S[i] - S[l];
            tsum += query(etc[l], etc[r], mn, mx);
            A[etc[i]] = sum - tsum;
        }
        A[min2[1]] = -1;
        A[max2[1]] = -1;
    }
    Solution(A + 1);
    return 0;
}

Compilation message

meandian.cpp: In function 'int main()':
meandian.cpp:77:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < etc.size(); ++i) {
                         ~~^~~~~~~~~~~~
meandian.cpp:81:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < etc.size(); ++i) {
                         ~~^~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 424 KB Output is correct
4 Correct 3 ms 316 KB Output is correct
5 Correct 3 ms 312 KB Output is correct
6 Correct 6 ms 248 KB Output is correct
7 Correct 8 ms 376 KB Output is correct
8 Correct 7 ms 320 KB Output is correct
9 Correct 7 ms 316 KB Output is correct
10 Correct 13 ms 444 KB Output is correct