답안 #142530

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
142530 2019-08-09T11:17:50 Z popovicirobert Meandian (CEOI06_meandian) C++14
100 / 100
14 ms 376 KB
/*
  CEOI 2006
  Competition Day #2
  Task MEANDIAN
  Sample library for C/C++
*/

/*
  input file format:
  N
  a1 a2 ... aN
*/

#include <bits/stdc++.h>
#include "libmean.h"

using namespace std;

const int INF = 1e9;
const int MAXN = 100;
int sol[MAXN];

inline int get(vector <int> a) {
    bool ok = 1;
    int i = 0;
    while(ok) {
        ok = 0, i++;
        for(auto it : a) {
            if(it == i) {
                ok = 1;
            }
        }
    }
    return i;
}

inline void del(vector <int> &a, int x) {
    vector <int> aux;
    for(auto it : a) {
        if(it != x) aux.push_back(it);
    }
    swap(a, aux);
}

int main() {
    int n, i, j;
    n = Init();

    vector <int> a = {1, 2, 3, 4};
    vector <int> b = a;
    int mn = Meandian(a[0], a[1], a[2], a[3]);
    int mx = mn;
    for(i = 5; i <= n; i++) {
        vector <int> aux = a;
        for(j = 0; j < 4; j++) {
            vector <int> cur;
            for(int k = 0; k < 4; k++) {
                cur.push_back(k != j ? a[k] : i);
            }
            int val = Meandian(cur[0], cur[1], cur[2], cur[3]);
            if(val < mn) {
                mn = val, aux = cur;
            }
        }
        a = aux;

        aux = b;
        for(j = 0; j < 4; j++) {
            vector <int> cur;
            for(int k = 0; k < 4; k++) {
                cur.push_back(k != j ? b[k] : i);
            }
            int val = Meandian(cur[0], cur[1], cur[2], cur[3]);
            if(val > mx) {
                mx = val, aux = cur;
            }
        }
        b = aux;
    }

    memset(sol, -1, sizeof(sol));
    if(n == 4) { Solution(sol); return 0; }

    int id_mn4, ga = get(a);
    mn = INF;
    for(i = 0; i < 4; i++) {
        vector <int> cur;
        for(j = 0; j < 4; j++) {
            cur.push_back(i != j ? a[j] : ga);
        }
        int val = Meandian(cur[0], cur[1], cur[2], cur[3]);
        if(val < mn) {
            mn = val, id_mn4 = a[i];
        }
    }
    del(a, id_mn4);

    int id_mx4, gb = get(b);
    mx = 0;
    for(i = 0; i < 4; i++) {
        vector <int> cur;
        for(j = 0; j < 4; j++) {
            cur.push_back(i != j ? b[j] : gb);
        }
        int val = Meandian(cur[0], cur[1], cur[2], cur[3]);
        if(val > mx) {
            mx = val, id_mx4 = b[i];
        }
    }
    del(b, id_mx4);

    int id_mn3; mn = INF;
    for(i = 0; i < 3; i++) {
        for(j = i + 1; j < 3; j++) {
            int val = Meandian(a[i], a[j], ga, id_mn4);
            if(val < mn) {
                mn = val, id_mn3 = a[3 - i - j];
            }
        }
    }
    del(a, id_mn3);

    int id_mx3; mx = 0;
    for(i = 0; i < 3; i++) {
        for(j = i + 1; j < 3; j++) {
            int val = Meandian(b[i], b[j], gb, id_mx4);
            if(val > mx) {
                mx = val, id_mx3 = b[3 - i - j];
            }
        }
    }
    del(b, id_mx3);

    vector <bool> vis(n + 1, 1);
    vis[a[0]] = vis[a[1]] = vis[b[0]] = vis[b[1]] = 0;

    vector <int> ids;
    for(i = 1; i <= n; i++) {
        if(vis[i]) ids.push_back(i);
    }

    int x = 2 * Meandian(a[0], a[1], b[0], b[1]);
    int y = 2 * Meandian(a[0], a[1], ids[0], b[0]);
    int z = 2 * Meandian(b[0], b[1], ids[0], a[0]);

    sol[ids[0] - 1] = (y + z - x) / 2;
    for(i = 1; i < ids.size(); i++) {
        sol[ids[i] - 1] = 2 * Meandian(a[0], b[0], ids[0], ids[i]) - sol[ids[0] - 1];
        //cerr << ids[i] << " " << a[0] << " " << b[0] << " " << ids[0] << "\n";
    }
    Solution(sol);

    return 0;
}

Compilation message

meandian.cpp: In function 'int main()':
meandian.cpp:148:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i = 1; i < ids.size(); i++) {
                ~~^~~~~~~~~~~~
meandian.cpp:133:8: warning: 'id_mx3' may be used uninitialized in this function [-Wmaybe-uninitialized]
     del(b, id_mx3);
     ~~~^~~~~~~~~~~
meandian.cpp:122:8: warning: 'id_mn3' may be used uninitialized in this function [-Wmaybe-uninitialized]
     del(a, id_mn3);
     ~~~^~~~~~~~~~~
meandian.cpp:111:8: warning: 'id_mx4' may be used uninitialized in this function [-Wmaybe-uninitialized]
     del(b, id_mx4);
     ~~~^~~~~~~~~~~
meandian.cpp:97:8: warning: 'id_mn4' may be used uninitialized in this function [-Wmaybe-uninitialized]
     del(a, id_mn4);
     ~~~^~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 4 ms 248 KB Output is correct
4 Correct 4 ms 248 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 7 ms 376 KB Output is correct
8 Correct 10 ms 248 KB Output is correct
9 Correct 14 ms 376 KB Output is correct
10 Correct 12 ms 376 KB Output is correct