Submission #111532

#	Time	Username	Problem	Language	Result	Execution time	Memory
111532		imaxblue	Circle selection (APIO18_circle_selection)	C++17	100 / 100	2811 ms	49392 KiB

circle_selection

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pll pair<ll, ll>
#define p3l pair<pll, ll>
#define vi vector<int>
#define vpii vector<pii>
#define vp3i vector<p3i>
#define vpll vector<pll>
#define vp3l vector<p3l>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define pq priority_queue
#define MN 1000000007
#define fox(k, x) for (int k=0; k<x; ++k)
#define fox1(k, x) for (int k=1; k<=x; ++k)
#define foxr(k, x) for (int k=x-1; k>=0; --k)
#define fox1r(k, x) for (int k=x; k>0; --k)
#define ms multiset
#define flood(x) memset(x, 0x3f3f3f3f, sizeof x)
#define drain(x) memset(x, 0, sizeof x)
#define rng() ((rand() << 14)+rand())
#define scan(X) do{while((X=getchar())<'0'); for(X-='0'; '0'<=(_=getchar()); X=(X<<3)+(X<<1)+_-'0');}while(0)
char _;
#define pi 3.14159265358979323846

int n, x[300005], y[300005], r[300005], sz;
int u[300005];
vector<pii> v;
vector<p3i> w;
vector<pair<int, vector<pair<int, vector<int> > > > > co;
void construct(){
  int X, Y, R, I;
  co.clear();
  //cout << "!" << endl;
  //cout << u[5] << ' ' <<w.size() << "%" << endl;
  w.clear();
  fox(l, n){
    if (u[l] == 0)
      w.pb(mp(mp(x[l]/sz, y[l]/sz), l));
  }
  sort(w.begin(), w.end());
  fox(l, w.size()){
    X = w[l].x.x; Y = w[l].x.y; I = w[l].y;
    //if (u[I]) continue;
    //cout << ' ' << X << ' ' << Y << ' ' << I << endl;
    if (co.empty() || co.back().x != X) co.pb(mp(X, vector<pair<int, vector<int> > >()));
    if (co.back().y.empty() || co.back().y.back().x != Y) co.back().y.pb(mp(Y, vector<int>()));
    //if (I==5 || I == 10) cout << "*" << X << ' ' << Y << ' ' << co.back().y.back().y.size()<< endl;
    co.back().y.back().y.pb(I);
    //if (I == 5 || ) cout << co.back().x << ' ' << co.back().y.back().x << ' ' << endl;
  }
}
void query(int P, int Cx, int Cy){
  int I, I2, P2;
  I = lb(co.begin(), co.end(), mp(Cx, vector<pair<int, vector<int> > >())) - co.begin();;
  if (I == co.size() || co[I].x != Cx) return;
  //if (P == 5) cout << "*";
  I2 = lb(co[I].y.begin(), co[I].y.end(), mp(Cy, vector<int>())) - co[I].y.begin();
  //if (P == 5) cout << I << ' ' << I2 << ' ' << co[I].y[I2].x << ' ' << Cy << endl;
  if (I2 == co[I].y.size() || co[I].y[I2].x != Cy) return;
  vector<int> tmp = co[I].y[I2].y;
  //if (P == 5) cout << tmp.size() << endl;
  fox(l, tmp.size()){
    P2 = tmp[l];
    //if (P == 5) cout << P2 << endl;
    if (u[P2]) continue;
    if (1LL*(x[P]-x[P2])*(x[P]-x[P2])+1LL*(y[P]-y[P2])*(y[P]-y[P2]) <= 1LL*(r[P]+r[P2])*(r[P]+r[P2])){
      u[P2] = P+1;
    }
  }
}
int32_t main(){
  scanf("%i", &n);
  sz = 2000000001;
  //co.pb(mp(0, vector<int>()));
  //co[0].y.pb(mp(0, vector<int>()));
  fox(l, n){
    scanf("%i %i %i", &x[l], &y[l], &r[l]);
    v.pb(mp(-r[l], l));
    w.pb(mp(mp(x[l], y[l]), l));
    //co[0].y[0].y.pb(l);
  }
  sort(v.begin(), v.end());
  sort(w.begin(), w.end());
  construct();
  fox(l, v.size()){
    v[l].x *= -1;
    if (u[v[l].y]) continue;
    while(v[l].x <= sz/4){
      //cout << v[l].x << ' ' << sz << endl;
      sz/=2;
      construct();
    }
    //cout << v[l].y << ' ' << sz << endl;
    //continue;
    query(v[l].y, x[v[l].y]/sz-1, y[v[l].y]/sz+1);
    query(v[l].y, x[v[l].y]/sz-1, y[v[l].y]/sz);
    query(v[l].y, x[v[l].y]/sz-1, y[v[l].y]/sz-1);
    query(v[l].y, x[v[l].y]/sz, y[v[l].y]/sz+1);
    query(v[l].y, x[v[l].y]/sz, y[v[l].y]/sz);
    query(v[l].y, x[v[l].y]/sz, y[v[l].y]/sz-1);
    query(v[l].y, x[v[l].y]/sz+1, y[v[l].y]/sz+1);
    query(v[l].y, x[v[l].y]/sz+1, y[v[l].y]/sz);
    query(v[l].y, x[v[l].y]/sz+1, y[v[l].y]/sz-1);
  }
  fox(l, n){
    printf("%i ", u[l]);
  }
  return 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
*/

Compilation message (stderr)

circle_selection.cpp: In function 'void construct()':
circle_selection.cpp:23:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
circle_selection.cpp:51:7:
   fox(l, w.size()){
       ~~~~~~~~~~~                 
circle_selection.cpp:51:3: note: in expansion of macro 'fox'
   fox(l, w.size()){
   ^~~
circle_selection.cpp:41:13: warning: unused variable 'R' [-Wunused-variable]
   int X, Y, R, I;
             ^
circle_selection.cpp: In function 'void query(int, int, int)':
circle_selection.cpp:65:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (I == co.size() || co[I].x != Cx) return;
       ~~^~~~~~~~~~~~
circle_selection.cpp:69:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (I2 == co[I].y.size() || co[I].y[I2].x != Cy) return;
       ~~~^~~~~~~~~~~~~~~~~
circle_selection.cpp:23:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
circle_selection.cpp:72:7:
   fox(l, tmp.size()){
       ~~~~~~~~~~~~~               
circle_selection.cpp:72:3: note: in expansion of macro 'fox'
   fox(l, tmp.size()){
   ^~~
circle_selection.cpp: In function 'int32_t main()':
circle_selection.cpp:23:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
circle_selection.cpp:95:7:
   fox(l, v.size()){
       ~~~~~~~~~~~                 
circle_selection.cpp:95:3: note: in expansion of macro 'fox'
   fox(l, v.size()){
   ^~~
circle_selection.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i", &n);
   ~~~~~^~~~~~~~~~
circle_selection.cpp:87:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i %i %i", &x[l], &y[l], &r[l]);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 30 / 30
• Subtask 6: 13 / 13