oj.uz

Submission #109056

# Submission time Handle Problem Language Result Execution time Memory
109056 2019-05-04T06:59:59 Z ryansee Circle selection (APIO18_circle_selection) C++14
30 / 100
 3000 ms 152100 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 66 ms 70776 KB Output is correct
2 Correct 67 ms 70780 KB Output is correct
3 Correct 87 ms 70860 KB Output is correct
4 Correct 84 ms 70904 KB Output is correct
5 Correct 78 ms 70776 KB Output is correct
6 Correct 79 ms 70868 KB Output is correct
7 Correct 74 ms 70808 KB Output is correct
8 Correct 79 ms 70776 KB Output is correct
9 Correct 85 ms 70832 KB Output is correct
10 Correct 67 ms 71000 KB Output is correct
11 Correct 177 ms 70904 KB Output is correct
12 Correct 175 ms 70876 KB Output is correct
13 Correct 220 ms 70776 KB Output is correct
14 Correct 185 ms 70920 KB Output is correct
15 Correct 187 ms 70892 KB Output is correct
16 Correct 138 ms 70964 KB Output is correct
17 Correct 71 ms 70904 KB Output is correct
18 Correct 75 ms 70876 KB Output is correct
19 Correct 78 ms 71160 KB Output is correct
20 Correct 70 ms 71288 KB Output is correct
21 Correct 157 ms 71544 KB Output is correct
22 Correct 330 ms 71672 KB Output is correct
23 Correct 303 ms 72056 KB Output is correct
24 Correct 290 ms 71800 KB Output is correct
25 Correct 274 ms 71544 KB Output is correct
26 Correct 351 ms 71676 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 451 ms 100420 KB Output is correct
2 Correct 417 ms 100716 KB Output is correct
3 Correct 301 ms 95712 KB Output is correct
4 Correct 336 ms 100236 KB Output is correct
5 Incorrect 846 ms 128352 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 70772 KB Output is correct
2 Correct 1982 ms 94980 KB Output is correct
3 Execution timed out 3104 ms 139744 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1040 ms 98364 KB Output is correct
2 Correct 1110 ms 109580 KB Output is correct
3 Correct 1592 ms 93408 KB Output is correct
4 Correct 971 ms 108516 KB Output is correct
5 Correct 1020 ms 109024 KB Output is correct
6 Correct 1188 ms 92136 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 70776 KB Output is correct
2 Correct 67 ms 70780 KB Output is correct
3 Correct 87 ms 70860 KB Output is correct
4 Correct 84 ms 70904 KB Output is correct
5 Correct 78 ms 70776 KB Output is correct
6 Correct 79 ms 70868 KB Output is correct
7 Correct 74 ms 70808 KB Output is correct
8 Correct 79 ms 70776 KB Output is correct
9 Correct 85 ms 70832 KB Output is correct
10 Correct 67 ms 71000 KB Output is correct
11 Correct 177 ms 70904 KB Output is correct
12 Correct 175 ms 70876 KB Output is correct
13 Correct 220 ms 70776 KB Output is correct
14 Correct 185 ms 70920 KB Output is correct
15 Correct 187 ms 70892 KB Output is correct
16 Correct 138 ms 70964 KB Output is correct
17 Correct 71 ms 70904 KB Output is correct
18 Correct 75 ms 70876 KB Output is correct
19 Correct 78 ms 71160 KB Output is correct
20 Correct 70 ms 71288 KB Output is correct
21 Correct 157 ms 71544 KB Output is correct
22 Correct 330 ms 71672 KB Output is correct
23 Correct 303 ms 72056 KB Output is correct
24 Correct 290 ms 71800 KB Output is correct
25 Correct 274 ms 71544 KB Output is correct
26 Correct 351 ms 71676 KB Output is correct
27 Correct 224 ms 72756 KB Output is correct
28 Correct 92 ms 71672 KB Output is correct
29 Correct 71 ms 71672 KB Output is correct
30 Correct 351 ms 73080 KB Output is correct
31 Correct 367 ms 72724 KB Output is correct
32 Correct 352 ms 72696 KB Output is correct
33 Correct 144 ms 78052 KB Output is correct
34 Correct 182 ms 78796 KB Output is correct
35 Correct 547 ms 106344 KB Output is correct
36 Correct 1197 ms 90088 KB Output is correct
37 Correct 1381 ms 90032 KB Output is correct
38 Correct 1557 ms 91356 KB Output is correct
39 Incorrect 1346 ms 152100 KB Output isn't correct
40 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 70776 KB Output is correct
2 Correct 67 ms 70780 KB Output is correct
3 Correct 87 ms 70860 KB Output is correct
4 Correct 84 ms 70904 KB Output is correct
5 Correct 78 ms 70776 KB Output is correct
6 Correct 79 ms 70868 KB Output is correct
7 Correct 74 ms 70808 KB Output is correct
8 Correct 79 ms 70776 KB Output is correct
9 Correct 85 ms 70832 KB Output is correct
10 Correct 67 ms 71000 KB Output is correct
11 Correct 177 ms 70904 KB Output is correct
12 Correct 175 ms 70876 KB Output is correct
13 Correct 220 ms 70776 KB Output is correct
14 Correct 185 ms 70920 KB Output is correct
15 Correct 187 ms 70892 KB Output is correct
16 Correct 138 ms 70964 KB Output is correct
17 Correct 71 ms 70904 KB Output is correct
18 Correct 75 ms 70876 KB Output is correct
19 Correct 78 ms 71160 KB Output is correct
20 Correct 70 ms 71288 KB Output is correct
21 Correct 157 ms 71544 KB Output is correct
22 Correct 330 ms 71672 KB Output is correct
23 Correct 303 ms 72056 KB Output is correct
24 Correct 290 ms 71800 KB Output is correct
25 Correct 274 ms 71544 KB Output is correct
26 Correct 351 ms 71676 KB Output is correct
27 Correct 451 ms 100420 KB Output is correct
28 Correct 417 ms 100716 KB Output is correct
29 Correct 301 ms 95712 KB Output is correct
30 Correct 336 ms 100236 KB Output is correct
31 Incorrect 846 ms 128352 KB Output isn't correct
32 Halted 0 ms 0 KB -