Submission #66132

#TimeUsernameProblemLanguageResultExecution timeMemory
66132BenqCircle selection (APIO18_circle_selection)C++11
100 / 100
2157 ms438336 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef long double ld; typedef complex<ld> cd; typedef pair<int, int> pi; typedef pair<ll,ll> pl; typedef pair<ld,ld> pd; typedef vector<int> vi; typedef vector<ld> vd; typedef vector<ll> vl; typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<cd> vcd; template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; #define FOR(i, a, b) for (int i=a; i<(b); i++) #define F0R(i, a) for (int i=0; i<(a); i++) #define FORd(i,a,b) for (int i = (b)-1; i >= a; i--) #define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--) #define sz(x) (int)(x).size() #define mp make_pair #define pb push_back #define f first #define s second #define lb lower_bound #define ub upper_bound #define all(x) x.begin(), x.end() const int MOD = 1000000007; const ll INF = 1e18; const int MX = 300001; const int CON = 1000000000; int n, r[MX], ans[MX]; pi p[MX]; set<pi> S; map<int,int> m; vi rm; vpi tmp[MX]; ll sq(ll x) { return x*x; } ll dist(pi a, pi b) { a.f -= b.f, a.s -= b.s; return (ll)a.f*a.f+(ll)a.s*a.s; } bool inter(int a, int b) { return dist(p[a],p[b]) <= sq(r[a]+r[b]); } void init() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; FOR(i,1,n+1) { //p[i].f = rand() % (2*CON); //p[i].s = rand() % (2*CON); //r[i] = rand() % CON+1; cin >> p[i].f >> p[i].s >> r[i]; p[i].f += CON; p[i].s += CON; S.insert({r[i],-i}); } } ll crad = INF; void del(int x, int e) { ans[x] = e; S.erase({r[x],-x}); } pi getPos(int x) { return {p[x].f/crad,p[x].s/crad}; } void recalc() { F0R(i,sz(m)) tmp[i].clear(); m.clear(), rm.clear(); FOR(i,1,n+1) if (!ans[i]) m[getPos(i).f] = 0; for (auto& a: m) { a.s = sz(rm); rm.pb(a.f); } FOR(i,1,n+1) if (!ans[i]) { pi P = getPos(i); tmp[m[P.f]].pb({P.s,i}); } F0R(i,sz(m)) sort(all(tmp[i])); } void solve() { pi x = *S.rbegin(); x.s *= -1; if (2*x.f <= crad) { crad = x.f; recalc(); } pi pos = getPos(x.s); int z = 0; for (int t = lb(all(rm),pos.f-2)-rm.begin(); t < sz(rm) && abs(rm[t]-pos.f) <= 2; t ++) for (int t2 = lb(all(tmp[t]),mp(pos.s-2,-MOD))-tmp[t].begin(); t2 < sz(tmp[t]) && abs(tmp[t][t2].f-pos.s) <= 2; t2++) { if (!ans[tmp[t][t2].s] && inter(x.s,tmp[t][t2].s)) { del(tmp[t][t2].s,x.s); z ++; } // if (x.s == 3905) cout << "HUH " << t << " " << t2 << " " << tmp[t][t2].s << "\n"; } /*if (z == 0) { cout << "OOPS " << inter(x.s,x.s) << "\n"; cout << "HUH " << x.s << " " << p[x.s].f << " " << p[x.s].s << " " << ans[x.s] << " " << r[x.s] << "\n"; cout << pos.f << " " << pos.s << " " << crad << "\n"; cout << m[pos.f] << "\n"; cout << lb(all(rm),pos.f-2)-rm.begin() << "\n"; exit(0); }*/ } int main() { init(); while (sz(S)) solve(); FOR(i,1,n+1) cout << ans[i] << " "; } /* Look for: * the exact constraints (multiple sets are too slow for n=10^6 :( ) * special cases (n=1?) * overflow (ll vs int?) * array bounds */
#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...