oj.uz

Submission #387875

# Submission time Handle Problem Language Result Execution time Memory
387875 2021-04-09T10:40:13 Z talant117408 Circle selection (APIO18_circle_selection) C++17
12 / 100
 1004 ms 39968 KB 
/*
    Code written by Talant I.D.
*/
#include <bits/stdc++.h>
 
using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
 
#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) int((v).size())
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define OK cout << "OK" << endl;
 
int mod;
 
ll mode(ll a) {
    a %= mod;
    if (a < 0) a += mod;
    return a;
}
 
ll subt(ll a, ll b) {
    return mode(mode(a)-mode(b));
}
 
ll add(ll a, ll b) {
    return mode(mode(a)+mode(b));
}
 
ll mult(ll a, ll b) {
    return mode(mode(a)*mode(b));
}
 
ll binpow(ll a, ll b, ll m) {
    ll res = 1;
    while (b) {
        if (b&1) res = ((res*a)%m+m)%m;
        a = ((a*a)%m+m)%m;
        b >>= 1;
    }
    return res;
}
  
void usaco(string s) {
    freopen((s+".in").c_str(), "r", stdin);
    freopen((s+".out").c_str(), "w", stdout);
}

const int N = 3e5+7;
int removedBy[N], adjacentTo[N], adjacentTimes[N];
int x[N], y[N], R[N];

bool intersect(int i1, int i2) {
	return ll((x[i1]-x[i2])*(x[i1]-x[i2])+(y[i1]-y[i2])*(y[i1]-y[i2])) <= ll((R[i1]+R[i2])*(R[i1]+R[i2]));
}

main() {
	do_not_disturb
    //~ usaco("marathon");
	
	int n;
	cin >> n;
	bool allZeroes = 1;
	for (int i = 0; i < n; i++) {
		cin >> x[i] >> y[i] >> R[i];
		if (y[i]) allZeroes = 0;
	}
	
	vector <pair <pii, pii>> points;
	auto cmp = [&](pair <pii, pii> a, pair <pii, pii> b) {
		if (a.first.first == b.first.first) return a.first.second < b.first.second;
		return a.first.first > b.first.first;
	};
	
	if (allZeroes) {
		for (int i = 0; i < n; i++) {
			points.pb(mp(mp(R[i], i+1), mp(x[i]-R[i], x[i]+R[i])));
		}
		sort(all(points), cmp);
		set <pii> byL, byR;
		for (auto to : points) byL.insert(mp(to.second.first, to.first.second));
		for (auto to : points) byR.insert(mp(to.second.second, to.first.second));
		
		for (auto to : points) {
			auto l = to.second.first, r = to.second.second;
			auto ind = to.first.second;
			if (removedBy[ind]) {
				continue;
			}
			auto it = byL.lb(mp(l, 0));
			while (it != byL.end() && (*it).first <= r) {
				removedBy[(*it).second] = ind;
				byR.erase(mp(x[(*it).second-1]+R[(*it).second-1], (*it).second));
				byL.erase(it);
				it = byL.lb(mp(l, 0));
			}
			auto it2 = byR.ub(mp(r, 2e9));
			while (it2 != byR.begin() && (*--it2).first >= l) {
				removedBy[(*it2).second] = ind;
				byL.erase(mp(x[(*it2).second-1]-R[(*it2).second-1], (*it2).second));
				byR.erase(it2);
				it2 = byR.ub(mp(r, 2e9));
			}
		}
	}
	else {
		for (int i = 0; i < n; i++) {
			points.pb(mp(mp(R[i], i+1), mp(x[i]-R[i], x[i]+R[i])));
		}
		sort(all(points), cmp);
		set <pii> markers;
		vector <pair <int, pii>> Ys;
		for (int i = 0; i < n; i++) {
			Ys.pb(mp(y[i]-R[i], mp(0, i)));
			Ys.pb(mp(y[i]+R[i], mp(1, i)));
		}
		sort(all(Ys));
		for (int i = 0; i < n*2; i++) {
			auto type = Ys[i].second.first, ind = Ys[i].second.second;
			if (!type) {
				markers.insert(mp(x[ind], ind));
				auto it = markers.lb(mp(x[ind], ind));
				if (it != markers.begin()) {
					auto pr = next(it, -1);
					if (intersect((*it).second, (*pr).second)) {
						adjacentTo[(*it).second] = (*pr).second+1;
						adjacentTo[(*pr).second] = (*it).second+1;
						adjacentTimes[(*it).second]++;
						adjacentTimes[(*pr).second]++;
					}
				}
				if (next(it, 1) != markers.end()) {
					auto nx = next(it, 1);
					if (intersect((*it).second, (*nx).second)) {
						adjacentTo[(*it).second] = (*nx).second+1;
						adjacentTo[(*nx).second] = (*it).second+1;
						adjacentTimes[(*it).second]++;
						adjacentTimes[(*nx).second]++;
					}
				}
			}
			else {
				auto it = markers.lb(mp(x[ind], ind));
				if (it != markers.begin() && next(it, 1) != markers.end()) {
					auto nx = next(it, 1);
					auto pr = next(it, -1);
					if (intersect((*nx).second, (*pr).second)) {
						adjacentTo[(*nx).second] = (*pr).second+1;
						adjacentTo[(*pr).second] = (*nx).second+1;
						adjacentTimes[(*nx).second]++;
						adjacentTimes[(*pr).second]++;
					}
				}
				markers.erase(it);
			}
		}
		
		bool onlyOne = 1;
		for (int i = 0; i < n; i++) {
			if (adjacentTimes[i] > 1) onlyOne = 0;
		}
		if (!onlyOne) return 0;
		for (int i = 0; i < n; i++) {
			auto ind = points[i].first.second;
			if (removedBy[ind]) continue;
			removedBy[ind] = ind;
			removedBy[adjacentTo[ind-1]] = ind;
		}
	}
	
	for (int i = 1; i <= n; i++) {
		cout << removedBy[i] << ' ';
	}
		
    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

circle_selection.cpp:69:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   69 | main() {
      |      ^
circle_selection.cpp: In function 'void usaco(std::string)':
circle_selection.cpp:57:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   57 |     freopen((s+".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:58:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   58 |     freopen((s+".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 292 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1004 ms 39948 KB Output is correct
2 Correct 994 ms 39960 KB Output is correct
3 Correct 1000 ms 39680 KB Output is correct
4 Correct 866 ms 39948 KB Output is correct
5 Correct 821 ms 39720 KB Output is correct
6 Correct 928 ms 39916 KB Output is correct
7 Correct 732 ms 39844 KB Output is correct
8 Correct 872 ms 39968 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 292 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 292 KB Output isn't correct
3 Halted 0 ms 0 KB -