Submission #1194625

#TimeUsernameProblemLanguageResultExecution timeMemory
1194625steveonalexTowns (IOI15_towns)C++20
61 / 100
9 ms328 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...