oj.uz

Submission #732745

# Submission time Handle Problem Language Result Execution time Memory
732745 2023-04-29T08:54:03 Z minhcool Circle selection (APIO18_circle_selection) C++17
38 / 100
 2230 ms 81896 KB 
#include<bits/stdc++.h>
using namespace std;
 
//#define int long long
#define fi first
#define se second
#define pb push_back
//#define mp make_pair
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 3e5 + 5;
 
const int oo = 1e18 + 7, mod = 1e9 + 7;
 
int n, x[N], y[N], r[N];
 
int ans[N];
 
bool out[N];
 
unordered_map<int, int> mp;
vector<ii> vc[N];
 
bool ck(int i, int j){
//	cout << i << " " << j << "\n";
	long long dist = (1LL * (x[i] - x[j]) * (x[i] - x[j]) + 1LL * (y[i] - y[j]) * (y[i] - y[j]));
	long long rd = 1LL * (r[i] + r[j]) * (r[i] + r[j]);
	return (dist <= rd);
}
 
void process(){
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> x[i] >> y[i] >> r[i];
	set<ii> rem;
	for(int i = 1; i <= n; i++) rem.insert({-r[i], i});
	bool chk = 1;
	for(int i = 1; i <= n; i++) chk &= (r[i] == 1);
	if(chk){
		for(int i = 1; i <= n; i++) cout << i << " ";
		cout << "\n";
		exit(0);
	}
	for(int i = 30; i >= 0; i--){// executing with radius (1LL << (i - 1)) to (1LL << i)
		int rad = (1LL << i);
		mp.clear();
		for(int j = 1; j <= n; j++) vc[j].clear();
		vector<int> diff;
		for(int j = 1; j <= n; j++) if(!out[j]) diff.pb(x[j] / rad);
		sort(diff.begin(), diff.end());
		diff.resize(unique(diff.begin(), diff.end()) - diff.begin());
		for(int j = 0; j < diff.size(); j++) mp[diff[j]] = j + 1;
		for(int j = 1; j <= n; j++){
			if(!out[j]){
				//cout << "OK " << rad << " " << j << " " << x[j]/rad << " " << y[j] << "\n";
				vc[mp[x[j]/rad]].pb({y[j], j});
			}
		}
		for(int j = 1; j <= n; j++) sort(vc[j].begin(), vc[j].end());
		while(!rem.empty() && -((*rem.begin()).fi) >= (1LL << (i - 1))){
			int ind = (*rem.begin()).se;
		//	cout << rad << " " << ind << "\n";
			assert(!out[ind]);
			out[ind] = 1;
			ans[ind] = ind;
			rem.erase({-r[ind], ind});
			for(int i2 = x[ind]/rad - 5; i2 <= x[ind]/rad + 5; i2++){
				if(mp.find(i2) == mp.end()) continue;
				int temp = mp[i2];
				int le = (y[ind]/rad) - 5, ri = (y[ind] / rad) + 5;
			//	cout << 
				le *= rad, ri *= rad;
			//	cout << le << " " << ri << "\n";
				vector<ii>::iterator it = lower_bound(vc[temp].begin(), vc[temp].end(), make_pair(le, -oo));
				for(; it != vc[temp].end(); it++){
					if((*it).fi > ri) break;
					if(out[(*it).se]) continue;
					if(ck(ind, (*it).se)){
						//cout << ind << " " << (*it).se << "\n";
						ans[(*it).se] = ind;
						rem.erase({-r[(*it).se], (*it).se});
						out[(*it).se] = 1;
					}
				}
			}
		}
	}
	for(int i = 1; i <= n; i++) if(!ans[i]) ans[i] = i;
	for(int i = 1; i <= n; i++) cout << ans[i] << " ";
	cout << "\n";
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
    process();
}

Compilation message

circle_selection.cpp:16:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   16 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~
circle_selection.cpp: In function 'void process()':
circle_selection.cpp:54:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   for(int j = 0; j < diff.size(); j++) mp[diff[j]] = j + 1;
      |                  ~~^~~~~~~~~~~~~

Subtask #1
0 / 7.0

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

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 483 ms 34680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 395 ms 22140 KB Output is correct
3 Correct 1528 ms 59348 KB Output is correct
4 Correct 1460 ms 59492 KB Output is correct
5 Correct 1431 ms 52884 KB Output is correct
6 Correct 564 ms 32152 KB Output is correct
7 Correct 308 ms 20724 KB Output is correct
8 Correct 60 ms 10384 KB Output is correct
9 Correct 1647 ms 59308 KB Output is correct
10 Correct 1227 ms 50228 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1405 ms 59808 KB Output is correct
2 Correct 167 ms 26880 KB Output is correct
3 Correct 1006 ms 42272 KB Output is correct
4 Correct 1996 ms 73484 KB Output is correct
5 Correct 2230 ms 81896 KB Output is correct
6 Correct 869 ms 42772 KB Output is correct

Subtask #5
0 / 30.0

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

Subtask #6
0 / 13.0

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