제출 #109036

#제출 시각아이디문제언어결과실행 시간메모리
109036ryansee원 고르기 (APIO18_circle_selection)C++14
19 / 100
3091 ms62624 KiB
#include "bits/stdc++.h" using namespace std; #define FAST ios_base::sync_with_stdio(false); cin.tie(0); #define LLINF ((long long) 1e18)//1234567890987654321 #define INF 1234567890ll #define pb push_back #define ins insert #define f first #define s second #define db 0 #define EPS (1e-7) //0.0000001 the value #define PI (acos(-1)) #define MAXN (300006) #define MAXK 26 #define MAXX 15000006 #define ll long long int #define ld long double mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //can be used by calling rng() or shuffle(A, A+n, rng) #define FOR(ii, ss, ee) for(ll ii = ss; ii < ee; ++ii) #define space " " #define cbr cerr << "hi\n" #define mmst(x, v) memset((x), v, sizeof ((x))) #define siz(x) ((ll)x.size()) #define ph push #define btinpct(x) __builtin_popcountll(x) #define p2(x) (1LL<<(x)) #define all(x) (x).begin(), (x).end() #define lbd(x, y) lower_bound(all(x), y) #define ubd(x, y) upper_bound(all(x), y) typedef pair <ll, ll> pi; typedef pair <ll, pi> spi; typedef pair <pi, pi> dpi; inline ll rand(ll x, ll y) { ++y; return (rng() % (y-x)) + x; } //inclusivesss ll n; bool s2 = 1; pi A[MAXN], C[MAXN]; bool done[MAXN]; int ans[MAXN]; #define sq(x) ((x)*(x)) ld sqr(ll x) { return (x ? sqrtl(x) : 0); } ld mdist(ll a, ll b, ll c, ll d) { return sqr( sq(llabs(a-c)) + sq(llabs(b-d)) ); } string st1() { sort(A,A+n, [] (pi x, pi y) { if(x.f!=y.f) return x.f > y.f; else return x.s < y.s; } ); FOR(ii,0,n) { ll i = A[ii].s; ll r = A[ii].f; if(done[i]) continue; ans[i] = i; FOR(j,ii+1,n) { if(!done[A[j].s] && mdist(C[i].f,C[i].s,C[A[j].s].f,C[A[j].s].s) <= (ld)r + (ld)A[j].f) { done[A[j].s] = 1; ans[A[j].s] = i; } } } FOR(i,0,n) cout << ans[i] + 1 << ' '; cout << '\n'; string s = ""; FOR(i,0,n) s += to_string(ans[i]+1); return s; } string st2() { sort(A,A+n, [] (pi x, pi y) { if(x.f!=y.f) return x.f > y.f; else return x.s < y.s; } ); mmst(ans,0); multiset <pi> ms_smol,ms_big; // x-coord, radius, index FOR(i,0,n) { ms_smol.ins(pi(C[A[i].s].f+A[i].f, i)); ms_big.ins(pi(C[A[i].s].f-A[i].f, i)); } FOR(i,0,n) { if(ms_smol.find(pi(C[A[i].s].f+A[i].f, i)) == ms_smol.end()) { continue; } while(1) { auto itrrr = ms_big.find(pi(C[A[i].s].f-A[i].f, i)); auto itr2 = next(itrrr); if(itr2==ms_big.end()) break; if(C[A[i].s].f + A[i].f >= itr2->f) { ans[A[itr2->s].s] = A[i].s; ms_smol.erase(ms_smol.find(pi(C[A[itr2->s].s].f+A[itr2->s].f, itr2->s))); ms_big.erase(itr2); } else break; } while(1) { auto itrrr = ms_smol.find(pi(C[A[i].s].f+A[i].f, i)); if(itrrr==ms_smol.begin()) break; auto itr2 = prev(itrrr); if(C[A[i].s].f - A[i].f <= itr2->f) { ans[A[itr2->s].s] = A[i].s; ms_smol.erase(itr2); ms_big.erase(ms_big.find(pi(C[A[itr2->s].s].f-A[itr2->s].f, itr2->s))); } else break; } ms_smol.erase(ms_smol.find(pi(C[A[i].s].f+A[i].f,i))); ms_big.erase(ms_big.find(pi(C[A[i].s].f-A[i].f,i))); ans[A[i].s] = A[i].s; } FOR(i,0,n) cout << ans[i]+1 << ' '; cout << '\n'; string s = ""; FOR(i,0,n) s += to_string(ans[i]+1); return s; } // ll mdist(ll a, ll b, ll c, ll d) { return llabs(a-c)+llabs(b-d); } void st3() { vector<ll>inter(n,0); vector<bool>re(n,0); set <pi> ms; vector <pi> events; FOR(i,0,n) events.pb(pi(C[i].s-A[i].f,i)), events.pb(pi(C[i].s+A[i].f,-i-1)); sort(all(events), [] (pi x, pi y) { if(x.f != y.f) return x.f < y.f; else return x.s > y.s; } ); for(auto j : events) { ll i = j.s; if(i>=0) { ll r = A[i].f; ll x = C[i].f; bool in = 1; pi near = pi(LLINF, LLINF); if(!ms.empty()) { // pi near = LLINF; auto itr = ms.lower_bound(pi(x,0)); if(itr != ms.end()) near = min(near, pi(mdist(C[itr->s].f,C[itr->s].s, C[i].f, C[i].s)-(ld)A[itr->s].f, itr->s)); if(itr != ms.begin()) { --itr; near = min(near, pi(mdist(C[itr->s].f,C[itr->s].s, C[i].f, C[i].s)-(ld)A[itr->s].f, itr->s)); } assert(near.f != LLINF); if(near.f-EPS <= (ld)r) in = 0; } if(in) { ms.ins(pi(x,i)); re[i] = 1; } else { re[i] = 0; assert(re[near.s]); assert((ms.find(pi(C[near.s].f, near.s))!=ms.end())); // assert(ms.find(pi(C[near.s].f+A[near.s].f, near.s))!=ms.end()); ms.erase(ms.find(pi(C[near.s].f, near.s))); // ms.erase(ms.find(pi(C[near.s].f+A[near.s].f, near.s))); re[near.s] = 0; inter[i] = near.s; inter[near.s] = i; } } else { i = -i-1; if(re[i] == 0) continue; ll r = A[i].f; ll x = C[i].f; ms.erase(ms.find(pi(x,i))); // bool in = 1; pi near = pi(LLINF, LLINF); // if(!ms.empty()) { // // pi near = LLINF; // auto itr = ms.lower_bound(pi(x,0)); // if(itr != ms.end()) near = min(near, pi(mdist(C[itr->s].f,C[itr->s].s, C[i].f, C[i].s)-(ld)A[itr->s].f, itr->s)); // if(itr != ms.begin()) { --itr; near = min(near, pi(mdist(C[itr->s].f,C[itr->s].s, C[i].f, C[i].s)-(ld)A[itr->s].f, itr->s)); } // assert(near.f != LLINF); // if(near.f-EPS <= (ld)r) in = 0; // } // if(!in) { // re[i] = 0; assert(re[near.s]); // assert((ms.find(pi(C[near.s].f, near.s))!=ms.end())); // // assert(ms.find(pi(C[near.s].f+A[near.s].f, near.s))!=ms.end()); // ms.erase(ms.find(pi(C[near.s].f, near.s))); // // ms.erase(ms.find(pi(C[near.s].f+A[near.s].f, near.s))); // re[near.s] = 0; // inter[i] = near.s; // inter[near.s] = i; // } auto itr = ms.lower_bound(pi(x,0)); if(itr != ms.end()) assert(itr->f > x); if(itr != ms.begin() && itr != ms.end()) { ll a = prev(itr)->s, b = itr->s; if(mdist(C[a].f,C[a].s,C[b].f,C[b].s) <= (ld)A[a].f + (ld)A[b].f){ re[a] = re[b] = 0; inter[a] = b; inter[b] = a; itr=ms.erase(prev(itr)); ms.erase(itr); } } } } FOR(i,0,n) ans[i] = i; FOR(i,0,n) if(!re[i]&&(A[inter[i]].f>A[i].f||(A[inter[i]].f==A[i].f&&inter[i]<i))) { ans[i] = inter[i]; } FOR(i,0,n) cout << ans[i]+1 << ' '; cout<<'\n'; } vector<pi>in; bool s4 = 1; ll R = -1; ll magic = 5; // odd number pls bool inter(ll i, ll j) { if(done[j]) return 1; if(mdist(C[i].f, C[i].s, C[j].f, C[j].s) <= (ld)A[i].f + (ld) A[j].f) { // assert(i < j); done[j] = 1; ans[j] = i; return 1; } else return 0; } unordered_map <ll, int> mp; vector <ll> d; set<pi>ind[MAXN]; void split() { } void st4() { FOR(i,0,n) { d.pb(C[i].f/R); } sort(all(d)); d.resize(unique(all(d))-d.begin()); ll co = 1; for(auto i : d) mp[i] = co++; FOR(i,0,n) { ind[mp[C[i].f/R]].ins(pi(C[i].s,i)); } int p[n+5]; for(ll i=0;i<n;i++) p[i]=i; sort(p,p+n,[](ll x, ll y){if(A[x].f==A[y].f)return A[x].s<A[y].s; else return A[x].f>A[y].f;}); // assert(ind[0].empty()); FOR(iii,0,n) { ll i = p[iii]; // cerr << i+1 << ' '; if(done[i]) continue; done[i] = 1; ans[i] = i; if(A[i].f < R/2) { split(); } ll x = mp[C[i].f/R], y = C[i].s; // ind[x].erase(ind[x].find(pi(y,i))); ll ii = i; FOR(i,x-magic/2,x+magic/2+1) { if(i <= 0 || i > siz(d) )continue; // ll d = llabs(x-i) * R + R; // auto lower = ind[i].lower_bound(pi(sqr((4ll*sq(R))-sq(d))-y, 0)); // auto upper = (ind[i].upper_bound(pi(sqr((4ll*sq(R))-sq(d))+y, LLINF))); // if(upper != ind[i].end() && pi(lower->f,lower->s) > pi(upper->f,upper->s)) continue; // if(lower == ind[i].end()) continue; for(auto j = ind[i].begin(); j != ind[i].end();) { if(inter(ii,j->s)) { j=ind[i].erase(j); } else ++j; } } } FOR(i,0,n) assert(done[i]); FOR(i,0,n) cout << ans[i] + 1 << ' '; } int main() { // freopen("int","r",stdin); freopen("out","w",stdout); FAST cin >> n; FOR(i,0,n) { cin >> C[i].f >> C[i].s >> A[i].f; if(0)in.pb(pi(C[i].f,A[i].f)); if(C[i].s) s2 = 0; A[i].s = i; if(R == -1) R = A[i].f; if(R != A[i].f) s4 = 0; R=max(R,A[i].f); } // if(st1() != st2()) { // cerr << n << '\n'; // for(auto i : in) cerr << i.f << ' ' << i.s << '\n'; // assert(0); // } // assert(st1() == st2()); if(n <= 5000&&0) { st1(); } else if(s2&&0) { st2(); } else if(s4||1) { // becos i edited editorial solution here (the AC solution) st4(); }else { st3(); } } // 1 10 1 4 5 6 7 8 4 10 6 // 1 2 1 4 5 6 7 8 4 2 6 /* 3 5 0 3 10 0 2 20 0 8 4 1 0 3 10 0 5 15 0 1 20 0 10 8 1 4 14 12 6 10 0 6 14 0 9 6 3 2 0 0 * 11 9 9 2 13 2 1 11 8 2 3 3 2 3 12 1 12 14 1 9 8 5 2 8 2 5 2 1 14 4 2 14 14 1 */

컴파일 시 표준 에러 (stderr) 메시지

circle_selection.cpp: In function 'std::__cxx11::string st1()':
circle_selection.cpp:19:25: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 #define FOR(ii, ss, ee) for(ll ii = ss; ii < ee; ++ii)
                         ^
circle_selection.cpp:55:2: note: in expansion of macro 'FOR'
  FOR(i,0,n) cout << ans[i] + 1 << ' '; cout << '\n';
  ^~~
circle_selection.cpp:55:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  FOR(i,0,n) cout << ans[i] + 1 << ' '; cout << '\n';
                                        ^~~~
circle_selection.cpp: In function 'std::__cxx11::string st2()':
circle_selection.cpp:19:25: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 #define FOR(ii, ss, ee) for(ll ii = ss; ii < ee; ++ii)
                         ^
circle_selection.cpp:85:2: note: in expansion of macro 'FOR'
  FOR(i,0,n) cout << ans[i]+1 << ' '; cout << '\n';
  ^~~
circle_selection.cpp:85:38: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  FOR(i,0,n) cout << ans[i]+1 << ' '; cout << '\n';
                                      ^~~~
circle_selection.cpp: In function 'void st3()':
circle_selection.cpp:120:7: warning: unused variable 'r' [-Wunused-variable]
    ll r = A[i].f; ll x = C[i].f;
       ^
circle_selection.cpp:19:25: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 #define FOR(ii, ss, ee) for(ll ii = ss; ii < ee; ++ii)
                         ^
circle_selection.cpp:157:2: note: in expansion of macro 'FOR'
  FOR(i,0,n) cout << ans[i]+1 << ' '; cout<<'\n';
  ^~~
circle_selection.cpp:157:38: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  FOR(i,0,n) cout << ans[i]+1 << ' '; cout<<'\n';
                                      ^~~~
circle_selection.cpp: In function 'void st4()':
circle_selection.cpp:198:24: warning: unused variable 'y' [-Wunused-variable]
   ll x = mp[C[i].f/R], y = C[i].s;
                        ^
#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...