oj.uz

Submission #209222

# Submission time Handle Problem Language Result Execution time Memory
209222 2020-03-13T12:40:17 Z jtnydv25 Circle selection (APIO18_circle_selection) C++14
50 / 100
 1430 ms 47036 KB 
#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 q = lower_bound(all(points[p]), make_pair(y[pos] - 2 * R, -1)) - points[p].begin();
			while(q < sz(points[p]) && points[p][q].first <= y[pos] + 2 * R){
				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");
}

Compilation message

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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8568 KB Output is correct
2 Correct 10 ms 8568 KB Output is correct
3 Correct 10 ms 8568 KB Output is correct
4 Correct 12 ms 8568 KB Output is correct
5 Correct 11 ms 8568 KB Output is correct
6 Incorrect 12 ms 8568 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 31456 KB Output is correct
2 Correct 310 ms 31028 KB Output is correct
3 Correct 310 ms 29460 KB Output is correct
4 Correct 319 ms 30980 KB Output is correct
5 Correct 393 ms 36372 KB Output is correct
6 Correct 602 ms 35048 KB Output is correct
7 Correct 566 ms 39916 KB Output is correct
8 Correct 562 ms 37568 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8568 KB Output is correct
2 Correct 337 ms 20376 KB Output is correct
3 Correct 1430 ms 43672 KB Output is correct
4 Correct 1321 ms 43816 KB Output is correct
5 Correct 1208 ms 47036 KB Output is correct
6 Correct 318 ms 26816 KB Output is correct
7 Correct 154 ms 17620 KB Output is correct
8 Correct 33 ms 10232 KB Output is correct
9 Correct 1158 ms 47020 KB Output is correct
10 Correct 632 ms 42768 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 465 ms 31788 KB Output is correct
2 Correct 445 ms 36524 KB Output is correct
3 Correct 336 ms 30124 KB Output is correct
4 Correct 474 ms 36048 KB Output is correct
5 Correct 477 ms 36648 KB Output is correct
6 Correct 330 ms 29456 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8568 KB Output is correct
2 Correct 10 ms 8568 KB Output is correct
3 Correct 10 ms 8568 KB Output is correct
4 Correct 12 ms 8568 KB Output is correct
5 Correct 11 ms 8568 KB Output is correct
6 Incorrect 12 ms 8568 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8568 KB Output is correct
2 Correct 10 ms 8568 KB Output is correct
3 Correct 10 ms 8568 KB Output is correct
4 Correct 12 ms 8568 KB Output is correct
5 Correct 11 ms 8568 KB Output is correct
6 Incorrect 12 ms 8568 KB Output isn't correct
7 Halted 0 ms 0 KB -