#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MASK(i) (1ULL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll gcd(ll a, ll b){return __gcd(abs(a), abs(b));}
ll lcm(ll a, ll b){return abs(a) / gcd(a, b) * abs(b);}
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ull mask){return __builtin_popcountll(mask);}
int ctz(ull mask){return __builtin_ctzll(mask);}
int logOf(ull mask){return 63 - __builtin_clzll(mask);}
// mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
template <class T1, class T2>
bool maximize(T1 &a, T2 b){
if (a < b) {a = b; return true;}
return false;
}
template <class T1, class T2>
bool minimize(T1 &a, T2 b){
if (a > b) {a = b; return true;}
return false;
}
template <class T>
void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){
for(auto item: container) out << item << separator;
out << finish;
}
template <class T>
void remove_dup(vector<T> &a){
sort(ALL(a));
a.resize(unique(ALL(a)) - a.begin());
}
namespace Sub1{
int solve(int n){
int dih = 0;
int u = 0;
for(int i = 1; i < n; ++i) if (maximize(dih, getDistance(0, i)))
u = i;
int v = 0;
dih = 0;
vector<int> dis1(n);
for(int i = 0; i < n; ++i) if (i != u) {
dis1[i] = getDistance(i, u);
if (maximize(dih, dis1[i]))
v = i;
}
vector<int> dis2(n);
vector<int> left_dis(n), stick_out(n);
dis2[u] = dih;
left_dis[v] = dih;
int ans = 1e9 + 69;
for(int i = 0; i < n; ++i) if (i != u && i != v){
int x = dis1[i], y = dis2[i] = getDistance(i, v);
int cur = (x - y + dih) / 2;
stick_out[i] = dis1[i] - cur;
left_dis[i] = cur;
maximize(cur, dih - cur);
minimize(ans, cur);
}
vector<int> possible = left_dis; remove_dup(possible);
for(int i: possible){
if (max(i, dih - i) != ans) continue;
array<int, 3> cnt; fill(ALL(cnt), 0);
for(int j: left_dis) {
if (j < i) cnt[0]++;
else if (j == i) cnt[1]++;
else cnt[2]++;
}
if (*max_element(ALL(cnt)) <= n / 2) return ans;
}
return -ans;
}
}
namespace Sub2{
int solve(int n){
int dih = 0;
int u = 0;
for(int i = 1; i < n; ++i) if (maximize(dih, getDistance(0, i)))
u = i;
int v = 0;
dih = 0;
vector<int> dis1(n);
for(int i = 0; i < n; ++i) if (i != u) {
dis1[i] = getDistance(i, u);
if (maximize(dih, dis1[i]))
v = i;
}
vector<int> dis2(n);
vector<int> left_dis(n), stick_out(n);
dis2[u] = dih;
left_dis[v] = dih;
int ans = 1e9 + 69;
for(int i = 0; i < n; ++i) if (i != u && i != v){
int x = dis1[i], y = dis2[i] = getDistance(i, v);
int cur = (x - y + dih) / 2;
stick_out[i] = dis1[i] - cur;
left_dis[i] = cur;
maximize(cur, dih - cur);
minimize(ans, cur);
}
vector<int> possible = left_dis; remove_dup(possible);
for(int i: possible){
if (max(i, dih - i) != ans) continue;
array<int, 3> cnt; fill(ALL(cnt), 0);
vector<int> S;
for(int j = 0; j < n; ++j) {
if (left_dis[j] < i) cnt[0]++;
else if (left_dis[j] == i) {
cnt[1]++;
S.push_back(j);
}
else cnt[2]++;
}
if (*max_element(ALL(cnt)) <= n / 2) return ans;
if (max(cnt[0], cnt[2]) <= n / 2){
vector<int> st;
for(int j: S){
if (st.empty()) st.push_back(j);
else{
if (getDistance(st.back(), j) == stick_out[st.back()] + stick_out[j]) st.pop_back();
else st.push_back(j);
}
}
if (st.empty()) return ans;
int cnt = 0;
for(int j: S){
if (getDistance(st.back(), j) != stick_out[st.back()] + stick_out[j]) cnt++;
if (cnt > n / 2) break;
}
if (cnt <= n / 2) return ans;
}
}
return -ans;
}
}
int hubDistance(int n, int subtask){
if (subtask == 1 || subtask == 2 || subtask == 4) return Sub1::solve(n);
return Sub2::solve(n);
}
// int main(void){
// ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
// clock_t start = clock();
// cerr << "Time elapsed: " << clock() - start << " ms!\n";
// return 0;
// }
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |