제출 #209224

#제출 시각아이디문제언어결과실행 시간메모리
209224jtnydv25원 고르기 (APIO18_circle_selection)C++14
100 / 100
1345 ms66212 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define sd(x) scanf("%d", &(x)) #define pii pair<int, int> #define F first #define S second #define all(c) ((c).begin()), ((c).end()) #define sz(x) ((int)(x).size()) #define ld long double template<class T,class U> ostream& operator<<(ostream& os,const pair<T,U>& p){ os<<"("<<p.first<<", "<<p.second<<")"; return os; } template<class T> ostream& operator <<(ostream& os,const vector<T>& v){ os<<"{"; for(int i = 0;i < (int)v.size(); i++){ if(i)os<<", "; os<<v[i]; } os<<"}"; return os; } #ifdef LOCAL #define cerr cout #else #endif #define TRACE #ifdef TRACE #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__) template <typename Arg1> void __f(const char* name, Arg1&& arg1){ cerr << name << " : " << arg1 << std::endl; } template <typename Arg1, typename... Args> void __f(const char* names, Arg1&& arg1, Args&&... args){ const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...); } #else #define trace(...) #endif const int N = 300005; int x[N], y[N], r[N]; int where[N]; // compression vector<pii> points[N]; inline ll sq(int x){return x * (ll) x;} inline bool intersecting(int i, int j){ return sq(x[i] - x[j]) + sq(y[i] - y[j]) <= sq(r[i] + r[j]); } int daddy[N]; int main(){ memset(daddy, -1, sizeof daddy); int n; sd(n); for(int i = 0; i < n; i++){ sd(x[i]); sd(y[i]); sd(r[i]); } vector<int> perm(n), xsorted(n), ysorted(n); iota(all(perm), 0); iota(all(xsorted), 0); iota(all(ysorted), 0); stable_sort(all(perm), [](int i, int j){return r[i] > r[j];}); stable_sort(all(xsorted), [](int i, int j){return x[i] < x[j];}); stable_sort(all(ysorted), [](int i, int j){return y[i] < y[j];}); vector<int> compressedX; function<void(int)> compress = [&](int R){ for(int j = 0; j < sz(compressedX); j++) points[j].clear(); compressedX.clear(); int curr = x[xsorted[0]] / R; compressedX.push_back(curr); for(int i = 0; i < n; i++){ int pos = xsorted[i]; if(x[pos] / R == curr){ where[pos] = sz(compressedX) - 1; } else{ compressedX.push_back(curr = x[pos] / R); where[pos] = sz(compressedX) - 1; } } for(int pos : ysorted){ points[where[pos]].push_back({y[pos], pos}); } }; int R = 2000000001; for(int pos : perm){ if(daddy[pos] != -1) continue; if(2 * r[pos] < R){ R = r[pos]; compress(R); } daddy[pos] = pos; int p = lower_bound(all(compressedX), x[pos] / R - 2) - compressedX.begin(); int mx = x[pos] / R + 2; for(;p < sz(compressedX) && compressedX[p] <= mx; p++) if(!points[p].empty()){ int mn = y[pos] + 1e9 < 2 * R ? -1e9 - 10 : y[pos] - 2 * R; int mx = y[pos] - 1e9 > -2 * R ? 1e9 + 10 : y[pos] + 2 * R; int q = lower_bound(all(points[p]), make_pair(mn, -1)) - points[p].begin(); while(q < sz(points[p]) && points[p][q].first <= mx){ int t = points[p][q].S; if(daddy[t] == -1 && intersecting(pos, t)){ daddy[t] = pos; } q++; } } } for(int i = 0; i < n; i++) printf("%d ", daddy[i] + 1); printf("\n"); }

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

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sd(x) scanf("%d", &(x))
               ~~~~~^~~~~~~~~~~~
circle_selection.cpp:67:9: note: in expansion of macro 'sd'
  int n; sd(n);
         ^~
circle_selection.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sd(x) scanf("%d", &(x))
               ~~~~~^~~~~~~~~~~~
circle_selection.cpp:69:3: note: in expansion of macro 'sd'
   sd(x[i]); sd(y[i]); sd(r[i]);
   ^~
circle_selection.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sd(x) scanf("%d", &(x))
               ~~~~~^~~~~~~~~~~~
circle_selection.cpp:69:13: note: in expansion of macro 'sd'
   sd(x[i]); sd(y[i]); sd(r[i]);
             ^~
circle_selection.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sd(x) scanf("%d", &(x))
               ~~~~~^~~~~~~~~~~~
circle_selection.cpp:69:23: note: in expansion of macro 'sd'
   sd(x[i]); sd(y[i]); sd(r[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...