제출 #536401

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
536401		KoD	Towns (IOI15_towns)	C++17	컴파일 에러	0 ms	0 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
#include <cmath>

using std::array;
using std::pair;
using std::tuple;
using std::vector;

template <class F> bool majority(const int n, const F& f) {
    vector<int> list, bucket;
    for (int x = 0; x < n; ++x) {
        if (list.empty() || !f(list.back(), x)) {
            list.push_back(x);
            if (!bucket.empty()) {
                list.push_back(bucket.back());
                bucket.pop_back();
            }
        }
        else {
            bucket.push_back(x);
        }
    }
    const auto T = list.back();
    while (!list.empty()) {
        if (f(list.back(), T)) {
            if (list.size() == 1) {
                bucket.push_back(list.back());
                list.pop_back();
            }
            else {
                list.pop_back();
                list.pop_back();
            }
        }
        else {
            if (bucket.empty()) {
                return false;
            }
            list.pop_back();
            bucket.pop_back();
        }
    }
    return !bucket.empty();
}

int hubDistance(int N, int) {
    std::map<pair<int, int>, int> memo;
    const auto dist = [&](const int i, const int j) {
        assert(0 <= i and i < N);
        assert(0 <= j and j < N);
        if (i == j) {
            return 0;
        }
        const auto p = std::minmax(i, j);
        if (const auto itr = memo.find(p); itr != memo.end()) {
            return itr->second;
        }
        return memo[p] = getDistance(i, j);
    };

    int X = 0;
    for (int i = 1; i < N; ++i) {
        if (dist(0, X) < dist(0, i)) {
            X = i;
        }
    }
    int Y = 0;
    for (int i = 1; i < N; ++i) {
        if (dist(X, Y) < dist(X, i)) {
            Y = i;
        }
    }

    const int len = dist(0, X);
    const int diameter = dist(X, Y);

    const auto get_pos = [&](const int i) {
        const int l = dist(0, i);
        const int r = dist(X, i);
        const int d = (l + r - len) / 2;
        return r - d;
    };

    std::map<int, vector<int>> group;
    int min = 1000000000;
    for (int i = 0; i < N; ++i) {
        const int pos = get_pos(i);
        min = std::min(min, std::max(pos, diameter - pos));    
        group[pos].push_back(i);
    }

    int left = 0;
    vector<char> cand(N);
    for (const auto& [pos, list] : group) {
        const int n = (int)list.size();
        if (std::max(left, N - n - left) <= N / 2 and min == std::max(pos, diameter - pos)) {
            for (const int i : list) {
                cand[i] = true;
            }
        }
        left += n;
    }

    if (std::all_of(cand.begin(), cand.end(), [&](const char c) { return !c; }) {
        return -min;
    }
    return majority(N, [&](const int i, const int j) {
        const int pos = get_pos(i);
        return cand[i] and cand[j] and pos == get_pos(j) and dist(X, i) + dist(X, j) - dist(i, j) > 2 * pos;
    }) ? -min : min;
}

컴파일 시 표준 에러 (stderr) 메시지

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:105:80: error: expected ';' before '{' token
  105 |     if (std::all_of(cand.begin(), cand.end(), [&](const char c) { return !c; }) {
      |                                                                                ^~
      |                                                                                ;
towns.cpp:108:5: error: expected primary-expression before 'return'
  108 |     return majority(N, [&](const int i, const int j) {
      |     ^~~~~~
towns.cpp:107:6: error: expected ')' before 'return'
  107 |     }
      |      ^
      |      )
  108 |     return majority(N, [&](const int i, const int j) {
      |     ~~~~~~
towns.cpp:105:8: note: to match this '('
  105 |     if (std::all_of(cand.begin(), cand.end(), [&](const char c) { return !c; }) {
      |        ^
towns.cpp:111:20: warning: suggest braces around empty body in an 'if' statement [-Wempty-body]
  111 |     }) ? -min : min;
      |                    ^
towns.cpp:112:1: warning: no return statement in function returning non-void [-Wreturn-type]
  112 | }
      | ^