Submission #432673

#	Time	Username	Problem	Language	Result	Execution time	Memory
432673		2qbingxuan	Towns (IOI15_towns)	C++17	25 / 100	34 ms	848 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
#ifdef local
#define debug(a...) qqbx(#a, a)
#define pary(a...) danb(#a, a)
#define safe std::cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
template <typename ...T> void qqbx(const char *s, T ...a) {
    int cnt = sizeof...(T);
    ((std::cerr << "\e[1;32m(" << s << ") = ("), ..., (std::cerr << a << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename T> void danb(const char *s, T L, T R) {
    std::cerr << "\e[1;32m[ " << s << " ] = [ ";
    for (int f = 0; L != R; ++L)
        std::cerr << (f++ ? ", " : "") << *L;
    std::cerr << " ]\e[0m\n";
}
#else
#define debug(...) ((void)0)
#define pary(...) ((void)0)
#define safe ((void)0)
#endif // local
#define all(v) begin(v),end(v)

using namespace std;

map<pair<int,int>,int> asked;
int ask(int a, int b) {
    if (a == b) return 0;
    if (a > b) swap(a, b);
    if (asked.count({ a, b })) return asked[{ a, b }];
    return asked[{ a, b }] = getDistance(a, b);
}
int hubDistance(int N, int sub) {
    asked.clear();
    assert (1 <= sub && sub <= 6);
    int A = 0, B = 0;
    for (int i = 0; i < N; i++) {
        if (ask(0, i) > ask(0, A)) {
            A = i;
        }
    }
    for (int i = 0; i < N; i++) {
        if (ask(A, i) > ask(A, B)) {
            B = i;
        }
    }
    int R = ask(A, B);
    debug(A, B, R);
    for (int i = 0; i < N; i++) {
        // if (i == A || i == B) continue;
        int AB = ask(A, B);
        int AI = ask(A, i);
        int BI = ask(B, i);
        assert ((AB + abs(AI - BI)) % 2 == 0);
        R = min(R, (AB + abs(AI - BI)) / 2);
    }
    debug(R);
    return R;
}

• Subtask 1: 13 / 13
• Subtask 2: 12 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39