Submission #136299

#	Time	Username	Problem	Language	Result	Execution time	Memory
136299		imeimi2000	Meandian (CEOI06_meandian)	C++17	100 / 100	13 ms	444 KiB

meandian

#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 (stderr)

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 / 100