oj.uz

Submission #109055

# Submission time Handle Problem Language Result Execution time Memory
109055 2019-05-04T06:59:01 Z ryansee Circle selection (APIO18_circle_selection) C++14
42 / 100
 3000 ms 109536 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)*5
#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, ll> mp;
vector <ll> d;
vector<pi>ind[MAXN],tmp[MAXN];
ll latest = 0;
void split() { return;
	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 = -LLINF;
			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 != -LLINF) {
				// 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; assert(co+3 < MAXN);
			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 64 ms 70776 KB Output is correct
2 Correct 66 ms 70904 KB Output is correct
3 Correct 68 ms 70836 KB Output is correct
4 Correct 71 ms 70896 KB Output is correct
5 Correct 65 ms 70776 KB Output is correct
6 Correct 62 ms 70904 KB Output is correct
7 Correct 74 ms 70776 KB Output is correct
8 Correct 74 ms 70776 KB Output is correct
9 Correct 66 ms 71036 KB Output is correct
10 Correct 66 ms 70776 KB Output is correct
11 Correct 72 ms 70872 KB Output is correct
12 Correct 71 ms 70904 KB Output is correct
13 Correct 66 ms 70904 KB Output is correct
14 Correct 66 ms 70776 KB Output is correct
15 Correct 66 ms 70904 KB Output is correct
16 Correct 69 ms 71032 KB Output is correct
17 Correct 68 ms 70904 KB Output is correct
18 Correct 70 ms 70988 KB Output is correct
19 Correct 76 ms 71160 KB Output is correct
20 Correct 75 ms 71288 KB Output is correct
21 Correct 76 ms 71264 KB Output is correct
22 Correct 77 ms 71416 KB Output is correct
23 Correct 100 ms 71288 KB Output is correct
24 Correct 85 ms 71348 KB Output is correct
25 Correct 84 ms 71416 KB Output is correct
26 Correct 81 ms 71372 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 92484 KB Output is correct
2 Correct 285 ms 95116 KB Output is correct
3 Correct 321 ms 95756 KB Output is correct
4 Correct 316 ms 95332 KB Output is correct
5 Correct 398 ms 94728 KB Output is correct
6 Correct 748 ms 102284 KB Output is correct
7 Correct 456 ms 96992 KB Output is correct
8 Correct 553 ms 97572 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 70748 KB Output is correct
2 Correct 329 ms 79080 KB Output is correct
3 Correct 1582 ms 96044 KB Output is correct
4 Correct 1808 ms 96740 KB Output is correct
5 Execution timed out 3012 ms 93024 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1046 ms 98420 KB Output is correct
2 Correct 1146 ms 109536 KB Output is correct
3 Correct 1389 ms 93584 KB Output is correct
4 Correct 982 ms 108520 KB Output is correct
5 Correct 1004 ms 109088 KB Output is correct
6 Correct 1147 ms 92128 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 70776 KB Output is correct
2 Correct 66 ms 70904 KB Output is correct
3 Correct 68 ms 70836 KB Output is correct
4 Correct 71 ms 70896 KB Output is correct
5 Correct 65 ms 70776 KB Output is correct
6 Correct 62 ms 70904 KB Output is correct
7 Correct 74 ms 70776 KB Output is correct
8 Correct 74 ms 70776 KB Output is correct
9 Correct 66 ms 71036 KB Output is correct
10 Correct 66 ms 70776 KB Output is correct
11 Correct 72 ms 70872 KB Output is correct
12 Correct 71 ms 70904 KB Output is correct
13 Correct 66 ms 70904 KB Output is correct
14 Correct 66 ms 70776 KB Output is correct
15 Correct 66 ms 70904 KB Output is correct
16 Correct 69 ms 71032 KB Output is correct
17 Correct 68 ms 70904 KB Output is correct
18 Correct 70 ms 70988 KB Output is correct
19 Correct 76 ms 71160 KB Output is correct
20 Correct 75 ms 71288 KB Output is correct
21 Correct 76 ms 71264 KB Output is correct
22 Correct 77 ms 71416 KB Output is correct
23 Correct 100 ms 71288 KB Output is correct
24 Correct 85 ms 71348 KB Output is correct
25 Correct 84 ms 71416 KB Output is correct
26 Correct 81 ms 71372 KB Output is correct
27 Correct 79 ms 71692 KB Output is correct
28 Correct 83 ms 71672 KB Output is correct
29 Correct 89 ms 71672 KB Output is correct
30 Correct 90 ms 71672 KB Output is correct
31 Correct 71 ms 71800 KB Output is correct
32 Correct 79 ms 71928 KB Output is correct
33 Correct 152 ms 78040 KB Output is correct
34 Correct 155 ms 78744 KB Output is correct
35 Correct 184 ms 78532 KB Output is correct
36 Correct 291 ms 80492 KB Output is correct
37 Correct 275 ms 80396 KB Output is correct
38 Correct 366 ms 79848 KB Output is correct
39 Execution timed out 3026 ms 77400 KB Time limit exceeded
40 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 70776 KB Output is correct
2 Correct 66 ms 70904 KB Output is correct
3 Correct 68 ms 70836 KB Output is correct
4 Correct 71 ms 70896 KB Output is correct
5 Correct 65 ms 70776 KB Output is correct
6 Correct 62 ms 70904 KB Output is correct
7 Correct 74 ms 70776 KB Output is correct
8 Correct 74 ms 70776 KB Output is correct
9 Correct 66 ms 71036 KB Output is correct
10 Correct 66 ms 70776 KB Output is correct
11 Correct 72 ms 70872 KB Output is correct
12 Correct 71 ms 70904 KB Output is correct
13 Correct 66 ms 70904 KB Output is correct
14 Correct 66 ms 70776 KB Output is correct
15 Correct 66 ms 70904 KB Output is correct
16 Correct 69 ms 71032 KB Output is correct
17 Correct 68 ms 70904 KB Output is correct
18 Correct 70 ms 70988 KB Output is correct
19 Correct 76 ms 71160 KB Output is correct
20 Correct 75 ms 71288 KB Output is correct
21 Correct 76 ms 71264 KB Output is correct
22 Correct 77 ms 71416 KB Output is correct
23 Correct 100 ms 71288 KB Output is correct
24 Correct 85 ms 71348 KB Output is correct
25 Correct 84 ms 71416 KB Output is correct
26 Correct 81 ms 71372 KB Output is correct
27 Correct 352 ms 92484 KB Output is correct
28 Correct 285 ms 95116 KB Output is correct
29 Correct 321 ms 95756 KB Output is correct
30 Correct 316 ms 95332 KB Output is correct
31 Correct 398 ms 94728 KB Output is correct
32 Correct 748 ms 102284 KB Output is correct
33 Correct 456 ms 96992 KB Output is correct
34 Correct 553 ms 97572 KB Output is correct
35 Correct 60 ms 70748 KB Output is correct
36 Correct 329 ms 79080 KB Output is correct
37 Correct 1582 ms 96044 KB Output is correct
38 Correct 1808 ms 96740 KB Output is correct
39 Execution timed out 3012 ms 93024 KB Time limit exceeded
40 Halted 0 ms 0 KB -