제출 #1196198

#제출 시각아이디문제언어결과실행 시간메모리
1196198countlessCircle selection (APIO18_circle_selection)C++20
7 / 100
3095 ms22568 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; const ll MOD = 998244353; const ll INF = 1e18; const ld EPS = 1e-12; #define endl "\n" #define sp <<" "<< #define REP(i, a, b) for(ll i = a; i < b; i++) #define dbg(x) cout << #x << " = " << x << endl #define mp make_pair #define pb push_back #define fi first #define se second #define fast_io() ios_base::sync_with_stdio(false); cin.tie(NULL) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define sz(x) ((ll)(x).size()) struct custom_hash { static uint64_t splitmix64(uint64_t x) { // http://xorshift.di.unimi.it/splitmix64.c x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } }; template <typename Key, typename Value> using hash_map = unordered_map<Key, Value, custom_hash>; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); // uniform_int_distribution<int>(a, b)(rng); // shuffle(all(a), rng); struct circle { ld x, y, r, j; circle(ld x = 0, ld y = 0, ld r = 0) : x(x), y(y), r(r) {;;} bool operator<(const circle &other) const { if (r == other.r) return j > other.j; return r < other.r; } }; void solution() { int n; cin >> n; vector<circle> a(n); REP(i, 0, n) { cin >> a[i].x >> a[i].y >> a[i].r; a[i].j = i+1; } vector<int> ans(n+1); vector<bool> vis(n+1); iota(all(ans), 1); sort(rall(a)); auto intersect = [&](int i, int k) -> bool { ld dx = abs(a[i].x - a[k].x); ld dy = abs(a[i].y - a[k].y); return sqrtl(dx * dx + dy * dy) <= a[i].r + a[k].r; }; REP(i, 0, n) { if (vis[a[i].j]) continue; REP(k, 0, n) { if (vis[a[k].j]) continue; if (intersect(i, k)) { vis[a[k].j] = true; ans[a[k].j] = a[i].j; } } } REP(i, 1, n+1) { cout << ans[i] << " "; } cout << endl; return; } signed main() { fast_io(); solution(); return 0; } // Notes // is it binsearchable? // is it greedy? // is it DP? // if online round: search OEIS, similar topics // put observations together // check for edge cases // try "dumb" solutions, you're fast enough to rewrite // clean up the implementation // keep it simple // check for overflow // check for small N // check for array with same or monotonic a_i
#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...