oj.uz

Submission #109053

# Submission time Handle Problem Language Result Execution time Memory
109053 2019-05-04T06:56:08 Z ryansee Circle selection (APIO18_circle_selection) C++14
30 / 100
 3000 ms 95660 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, ll> mp;
vector <ll> d;
vector<pi>ind[MAXN],tmp[MAXN];
ll 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 = -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 16 ms 14464 KB Output is correct
2 Correct 15 ms 14464 KB Output is correct
3 Correct 23 ms 14464 KB Output is correct
4 Correct 18 ms 14464 KB Output is correct
5 Correct 14 ms 14464 KB Output is correct
6 Correct 18 ms 14464 KB Output is correct
7 Correct 16 ms 14464 KB Output is correct
8 Correct 16 ms 14464 KB Output is correct
9 Correct 19 ms 14464 KB Output is correct
10 Correct 17 ms 14464 KB Output is correct
11 Correct 25 ms 14464 KB Output is correct
12 Correct 36 ms 14464 KB Output is correct
13 Correct 32 ms 14464 KB Output is correct
14 Correct 36 ms 14464 KB Output is correct
15 Correct 40 ms 14456 KB Output is correct
16 Correct 27 ms 14592 KB Output is correct
17 Correct 16 ms 14592 KB Output is correct
18 Correct 20 ms 14592 KB Output is correct
19 Correct 22 ms 14848 KB Output is correct
20 Correct 20 ms 14848 KB Output is correct
21 Correct 32 ms 15096 KB Output is correct
22 Correct 66 ms 15352 KB Output is correct
23 Correct 83 ms 15736 KB Output is correct
24 Correct 79 ms 15352 KB Output is correct
25 Correct 70 ms 15232 KB Output is correct
26 Correct 59 ms 15356 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 44124 KB Output is correct
2 Correct 306 ms 44000 KB Output is correct
3 Correct 288 ms 39364 KB Output is correct
4 Correct 271 ms 43844 KB Output is correct
5 Incorrect 728 ms 71904 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 14464 KB Output is correct
2 Correct 1361 ms 38608 KB Output is correct
3 Execution timed out 3025 ms 83928 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 797 ms 42080 KB Output is correct
2 Correct 978 ms 53248 KB Output is correct
3 Correct 1211 ms 36960 KB Output is correct
4 Correct 842 ms 52148 KB Output is correct
5 Correct 873 ms 52720 KB Output is correct
6 Correct 1250 ms 35680 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14464 KB Output is correct
2 Correct 15 ms 14464 KB Output is correct
3 Correct 23 ms 14464 KB Output is correct
4 Correct 18 ms 14464 KB Output is correct
5 Correct 14 ms 14464 KB Output is correct
6 Correct 18 ms 14464 KB Output is correct
7 Correct 16 ms 14464 KB Output is correct
8 Correct 16 ms 14464 KB Output is correct
9 Correct 19 ms 14464 KB Output is correct
10 Correct 17 ms 14464 KB Output is correct
11 Correct 25 ms 14464 KB Output is correct
12 Correct 36 ms 14464 KB Output is correct
13 Correct 32 ms 14464 KB Output is correct
14 Correct 36 ms 14464 KB Output is correct
15 Correct 40 ms 14456 KB Output is correct
16 Correct 27 ms 14592 KB Output is correct
17 Correct 16 ms 14592 KB Output is correct
18 Correct 20 ms 14592 KB Output is correct
19 Correct 22 ms 14848 KB Output is correct
20 Correct 20 ms 14848 KB Output is correct
21 Correct 32 ms 15096 KB Output is correct
22 Correct 66 ms 15352 KB Output is correct
23 Correct 83 ms 15736 KB Output is correct
24 Correct 79 ms 15352 KB Output is correct
25 Correct 70 ms 15232 KB Output is correct
26 Correct 59 ms 15356 KB Output is correct
27 Correct 63 ms 16280 KB Output is correct
28 Correct 22 ms 15488 KB Output is correct
29 Correct 24 ms 15352 KB Output is correct
30 Correct 117 ms 16604 KB Output is correct
31 Correct 122 ms 16248 KB Output is correct
32 Correct 103 ms 16248 KB Output is correct
33 Correct 109 ms 21572 KB Output is correct
34 Correct 83 ms 22384 KB Output is correct
35 Correct 397 ms 49980 KB Output is correct
36 Correct 1240 ms 33516 KB Output is correct
37 Correct 1212 ms 33772 KB Output is correct
38 Correct 1133 ms 34928 KB Output is correct
39 Incorrect 1084 ms 95660 KB Output isn't correct
40 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14464 KB Output is correct
2 Correct 15 ms 14464 KB Output is correct
3 Correct 23 ms 14464 KB Output is correct
4 Correct 18 ms 14464 KB Output is correct
5 Correct 14 ms 14464 KB Output is correct
6 Correct 18 ms 14464 KB Output is correct
7 Correct 16 ms 14464 KB Output is correct
8 Correct 16 ms 14464 KB Output is correct
9 Correct 19 ms 14464 KB Output is correct
10 Correct 17 ms 14464 KB Output is correct
11 Correct 25 ms 14464 KB Output is correct
12 Correct 36 ms 14464 KB Output is correct
13 Correct 32 ms 14464 KB Output is correct
14 Correct 36 ms 14464 KB Output is correct
15 Correct 40 ms 14456 KB Output is correct
16 Correct 27 ms 14592 KB Output is correct
17 Correct 16 ms 14592 KB Output is correct
18 Correct 20 ms 14592 KB Output is correct
19 Correct 22 ms 14848 KB Output is correct
20 Correct 20 ms 14848 KB Output is correct
21 Correct 32 ms 15096 KB Output is correct
22 Correct 66 ms 15352 KB Output is correct
23 Correct 83 ms 15736 KB Output is correct
24 Correct 79 ms 15352 KB Output is correct
25 Correct 70 ms 15232 KB Output is correct
26 Correct 59 ms 15356 KB Output is correct
27 Correct 303 ms 44124 KB Output is correct
28 Correct 306 ms 44000 KB Output is correct
29 Correct 288 ms 39364 KB Output is correct
30 Correct 271 ms 43844 KB Output is correct
31 Incorrect 728 ms 71904 KB Output isn't correct
32 Halted 0 ms 0 KB -