제출 #209224

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
209224		jtnydv25	원 고르기 (APIO18_circle_selection)	C++14	100 / 100	1345 ms	66212 KiB

circle_selection

#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]);
                       ^~

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