oj.uz

Submission #109052

# Submission time Handle Problem Language Result Execution time Memory
109052 2019-05-04T06:52:18 Z ryansee Circle selection (APIO18_circle_selection) C++14
30 / 100
 3000 ms 95960 KB 
#include "bits/stdc++.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define LLINF ((long long) 1e18)//1234567890987654321
#define INF 1234567890ll
#define pb push_back
#define ins insert
#define f first
#define s second	
#define db 0
#define EPS (1e-7)    //0.0000001 the value
#define PI (acos(-1))
#define MAXN (300006)
#define MAXK 26
#define MAXX 15000006
#define ll long long int 
#define ld long double
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
#define FOR(ii, ss, ee) for(ll ii = ss; ii < ee; ++ii)
#define space " "
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ((ll)x.size())
#define ph push
#define btinpct(x) __builtin_popcountll(x)
#define p2(x) (1LL<<(x))
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
typedef pair <ll, ll> pi;
typedef pair <ll, pi> spi;
typedef pair <pi, pi> dpi;
inline ll rand(ll x, ll y) { ++y; return (rng() % (y-x)) + x; } //inclusivesss
ll n; bool s2 = 1;
pi A[MAXN], C[MAXN];
bool done[MAXN];
int ans[MAXN];
#define sq(x) ((x)*(x))
ld sqr(ll x) { return (x ? sqrtl(x) : 0); }
ld mdist(ll a, ll b, ll c, ll d) { return sqr( sq(llabs(a-c)) + sq(llabs(b-d)) ); }
vector<pi>in;
bool s4 = 1; ll R = -1;

ll magic = 5; // odd number pls
bool inter(ll i, ll j) {
	if(done[j]) return 1;
	if(mdist(C[i].f, C[i].s, C[j].f, C[j].s) <= (ld)A[i].f + (ld) A[j].f) {
// 		assert(i < j);
		done[j] = 1;
		ans[j] = i;
		return 1;
	}
	else return 0;
}

unordered_map <ll, int> mp;
vector <ll> d;
vector<pi>ind[MAXN],tmp[MAXN];
int latest = 0;
void split() { 
	FOR(i,0,MAXN) tmp[i].clear();
	ll new_R = R/2; // if(new_R%2)new_R++;
	ll co = 1;
	mp.clear();
	FOR(i,1,latest+1) {
		if(ind[i].empty()) continue; assert(co < MAXN);
		if(ind[i].size()==1) { mp[C[ind[i][0].s].f/new_R] = co; tmp[co++].pb(ind[i][0]); }
		else {
			ll one = LLINF;
			ll two = 0;
			for(auto j : ind[i]) two = max(two, C[j.s].f/new_R);
			for(auto j : ind[i]) one = min(one, C[j.s].f/new_R);
			ll three = -INF;
			for(auto j : ind[i]) three = ((C[j.s].f/new_R) != one && (C[j.s].f/new_R) != two) ? C[j.s].f/new_R : three;
			// if(three != -INF) {
				// for(auto j : ind[i]) {
					// cer
					// ll cmp = C[j.s].f/new_R;
					// if(one == cmp || two == cmp || three == cmp);
					// else {
						// cout << "BRUHHH\n";						
						// exit(0);
					// }
				// }
			// }
			// cerr << "1,2,3: " << one << ' ' << two << ' ' << three << '\n';
			int add = 0;
			for(auto j : ind[i]) {
				// cerr << C[j.s].f << ' ' << new_R << ' ' << C[j.s].f/new_R << ' ' << C[j.s].f/R << '\n';
				if(C[j.s].f/new_R == one) { mp[C[j.s].f/new_R] = co; tmp[co].pb(j); add = max(add, 1); }
				else if(C[j.s].f/new_R == two) { mp[C[j.s].f/new_R] = co + 1; tmp[co+1].pb(j); add=max(add,2);}
				else if(C[j.s].f/new_R == three) { mp[C[j.s].f/new_R] = co + 2; tmp[co+2].pb(j); add=3;}
				else assert(0);
			}
			// cerr << '\n' << '\n';
			co += add;
		}
	}
	R=new_R; latest = co-1;
			assert(co < MAXN);
	FOR(i,0,MAXN) ind[i]=tmp[i];
}
void st4() {
	FOR(i,0,n) {
		d.pb(C[i].f/R);
	}
	sort(all(d)); d.resize(unique(all(d))-d.begin());
	ll co = 1; for(auto i : d) mp[i] = co++; 
	FOR(i,0,n) {
		ind[mp[C[i].f/R]].pb(pi(C[i].s,i));
		latest = max(latest, mp[C[i].f/R]);
	}
	// FOR(i,1,latest+1) sort(all(ind[i]));
	int p[n+5];
	for(ll i=0;i<n;i++) p[i]=i;
	sort(p,p+n,[](ll x, ll y){if(A[x].f==A[y].f)return A[x].s<A[y].s; else return A[x].f>A[y].f;});
// 	assert(ind[0].empty());
	FOR(iii,0,n) {
		ll i = p[iii]; // cerr << i+1 << ' ';
		if(done[i]) continue;
		done[i] = 1;
		ans[i] = i; if(A[i].f < R/2) { split(); }
		ll x = mp[C[i].f/R], y = C[i].s;
		ll ii = i;
		FOR(i,x-magic/2,x+magic/2+1) {
			if(i <= 0)continue;
// 			ll d = llabs(x-i) * R + R;
// 			auto lower = ind[i].lower_bound(pi(sqr((4ll*sq(R))-sq(d))-y, 0));
// 			auto upper = (ind[i].upper_bound(pi(sqr((4ll*sq(R))-sq(d))+y, LLINF)));
// 			if(upper != ind[i].end() && pi(lower->f,lower->s) > pi(upper->f,upper->s)) continue;
// 			if(lower == ind[i].end()) continue;
			for(auto j = ind[i].begin(); j != ind[i].end();j++) {
				if(inter(ii,j->s)) {}
			}
		}
	}
	FOR(i,0,n) assert(done[i]);
	FOR(i,0,n) cout << ans[i] + 1 << ' ';
}
int main()
{
	// freopen("int","r",stdin); // freopen("out","w",stdout);
	FAST
	cin >> n;
	FOR(i,0,n) {
		cin >> C[i].f >> C[i].s >> A[i].f; if(0)in.pb(pi(C[i].f,A[i].f));
		C[i].f+=1e9;
		C[i].s+=1e9;
		if(C[i].s) s2 = 0;
		A[i].s = i;
		if(R == -1) R = A[i].f;
		if(R != A[i].f) s4 = 0;
		R=max(R,A[i].f);
	} // if(R%2)R++;
	// if(st1() != st2()) {
		
		// cerr << n << '\n';
		// for(auto i : in) cerr << i.f << ' ' << i.s << '\n';
		// assert(0);
	// }
	// assert(st1() == st2());
	st4();
}
// 1 10 1 4 5 6 7 8 4 10 6
// 1 2 1 4 5 6 7 8 4 2 6
/*


3
5 0 3
10 0 2
20 0 8

4
1 0 3
10 0 5
15 0 1
20 0 10


8
1 4
14 12
6 10
0 6
14 0
9 6
3 2
0 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: In function 'void st4()':
circle_selection.cpp:123:24: warning: unused variable 'y' [-Wunused-variable]
   ll x = mp[C[i].f/R], y = C[i].s;
                        ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 14464 KB Output is correct
2 Correct 19 ms 14464 KB Output is correct
3 Correct 20 ms 14464 KB Output is correct
4 Correct 22 ms 14464 KB Output is correct
5 Correct 17 ms 14464 KB Output is correct
6 Correct 15 ms 14464 KB Output is correct
7 Correct 15 ms 14464 KB Output is correct
8 Correct 14 ms 14464 KB Output is correct
9 Correct 16 ms 14464 KB Output is correct
10 Correct 14 ms 14464 KB Output is correct
11 Correct 28 ms 14524 KB Output is correct
12 Correct 34 ms 14464 KB Output is correct
13 Correct 29 ms 14464 KB Output is correct
14 Correct 31 ms 14464 KB Output is correct
15 Correct 26 ms 14464 KB Output is correct
16 Correct 24 ms 14592 KB Output is correct
17 Correct 14 ms 14592 KB Output is correct
18 Correct 16 ms 14592 KB Output is correct
19 Correct 21 ms 15076 KB Output is correct
20 Correct 19 ms 14968 KB Output is correct
21 Correct 28 ms 15352 KB Output is correct
22 Correct 63 ms 15468 KB Output is correct
23 Correct 72 ms 15752 KB Output is correct
24 Correct 84 ms 15452 KB Output is correct
25 Correct 69 ms 15360 KB Output is correct
26 Correct 76 ms 15480 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 44208 KB Output is correct
2 Correct 304 ms 44216 KB Output is correct
3 Correct 277 ms 39644 KB Output is correct
4 Correct 298 ms 44024 KB Output is correct
5 Incorrect 709 ms 72112 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 14464 KB Output is correct
2 Correct 1399 ms 38736 KB Output is correct
3 Execution timed out 3104 ms 84700 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 742 ms 42248 KB Output is correct
2 Correct 947 ms 53328 KB Output is correct
3 Correct 1554 ms 37216 KB Output is correct
4 Correct 931 ms 52140 KB Output is correct
5 Correct 1014 ms 52808 KB Output is correct
6 Correct 1122 ms 35680 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 14464 KB Output is correct
2 Correct 19 ms 14464 KB Output is correct
3 Correct 20 ms 14464 KB Output is correct
4 Correct 22 ms 14464 KB Output is correct
5 Correct 17 ms 14464 KB Output is correct
6 Correct 15 ms 14464 KB Output is correct
7 Correct 15 ms 14464 KB Output is correct
8 Correct 14 ms 14464 KB Output is correct
9 Correct 16 ms 14464 KB Output is correct
10 Correct 14 ms 14464 KB Output is correct
11 Correct 28 ms 14524 KB Output is correct
12 Correct 34 ms 14464 KB Output is correct
13 Correct 29 ms 14464 KB Output is correct
14 Correct 31 ms 14464 KB Output is correct
15 Correct 26 ms 14464 KB Output is correct
16 Correct 24 ms 14592 KB Output is correct
17 Correct 14 ms 14592 KB Output is correct
18 Correct 16 ms 14592 KB Output is correct
19 Correct 21 ms 15076 KB Output is correct
20 Correct 19 ms 14968 KB Output is correct
21 Correct 28 ms 15352 KB Output is correct
22 Correct 63 ms 15468 KB Output is correct
23 Correct 72 ms 15752 KB Output is correct
24 Correct 84 ms 15452 KB Output is correct
25 Correct 69 ms 15360 KB Output is correct
26 Correct 76 ms 15480 KB Output is correct
27 Correct 53 ms 16620 KB Output is correct
28 Correct 22 ms 15616 KB Output is correct
29 Correct 28 ms 15608 KB Output is correct
30 Correct 104 ms 16888 KB Output is correct
31 Correct 101 ms 16504 KB Output is correct
32 Correct 112 ms 16328 KB Output is correct
33 Correct 102 ms 22380 KB Output is correct
34 Correct 92 ms 23260 KB Output is correct
35 Correct 364 ms 50908 KB Output is correct
36 Correct 1320 ms 34364 KB Output is correct
37 Correct 1217 ms 34504 KB Output is correct
38 Correct 1260 ms 35848 KB Output is correct
39 Incorrect 1213 ms 95960 KB Output isn't correct
40 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 14464 KB Output is correct
2 Correct 19 ms 14464 KB Output is correct
3 Correct 20 ms 14464 KB Output is correct
4 Correct 22 ms 14464 KB Output is correct
5 Correct 17 ms 14464 KB Output is correct
6 Correct 15 ms 14464 KB Output is correct
7 Correct 15 ms 14464 KB Output is correct
8 Correct 14 ms 14464 KB Output is correct
9 Correct 16 ms 14464 KB Output is correct
10 Correct 14 ms 14464 KB Output is correct
11 Correct 28 ms 14524 KB Output is correct
12 Correct 34 ms 14464 KB Output is correct
13 Correct 29 ms 14464 KB Output is correct
14 Correct 31 ms 14464 KB Output is correct
15 Correct 26 ms 14464 KB Output is correct
16 Correct 24 ms 14592 KB Output is correct
17 Correct 14 ms 14592 KB Output is correct
18 Correct 16 ms 14592 KB Output is correct
19 Correct 21 ms 15076 KB Output is correct
20 Correct 19 ms 14968 KB Output is correct
21 Correct 28 ms 15352 KB Output is correct
22 Correct 63 ms 15468 KB Output is correct
23 Correct 72 ms 15752 KB Output is correct
24 Correct 84 ms 15452 KB Output is correct
25 Correct 69 ms 15360 KB Output is correct
26 Correct 76 ms 15480 KB Output is correct
27 Correct 369 ms 44208 KB Output is correct
28 Correct 304 ms 44216 KB Output is correct
29 Correct 277 ms 39644 KB Output is correct
30 Correct 298 ms 44024 KB Output is correct
31 Incorrect 709 ms 72112 KB Output isn't correct
32 Halted 0 ms 0 KB -