Submission #432698

#	Time	Username	Problem	Language	Result	Execution time	Memory
432698		2qbingxuan	Towns (IOI15_towns)	C++17	35 / 100	22 ms	460 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);
    vector<pair<int,int>> pos(N);
    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);
        pos[i] = { (AB + AI - BI) / 2, (AB + abs(AI - BI)) / 2 };
    }
    sort(all(pos));
    bool bal = false;
    for (int i = 0, j = 0; i < N; i = j) {
        for (j = i; j < N; j++) if (pos[i].first != pos[j].first) break;
        int RR = pos[i].second;
        if (i <= N / 2 && N - j <= N / 2 && RR == R && j-i <= N / 2) {
            bal = true;
        }
    }
    debug(R);
    return bal ? R : -R;
}

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