Submission #109083

#	Time	Username	Problem	Language	Result	Execution time	Memory
109083		ryansee	Circle selection (APIO18_circle_selection)	C++14	87 / 100	2957 ms	97164 KiB

circle_selection

#pragma GCC target ("avx2")
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
 
#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; int R = -1;
	#define sdb __attribute((optimize("-Ofast"), target("arch=sandybridge")))
ll magic = 5; // odd number pls
inline bool sdb inter(int i, int 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;
}
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
 
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
unordered_map <int, int, custom_hash> mp;
vector <int> d;
vector<pi>ind[MAXN],tmp[MAXN];
int latest = 0;
void sdb split() { 
	FOR(i,0,latest+1) 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()) { assert(0); continue; } assert(co < MAXN);
		if(ind[i].size()==1) { if(mp[C[ind[i][0].s].f/new_R] == 0) mp[C[ind[i][0].s].f/new_R] = co++; tmp[mp[C[ind[i][0].s].f/new_R]].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';
			if(one == two) { // 1
				assert(three==-LLINF);
				if(mp[one]==0)mp[one] = co ++;
			} else if(three == -LLINF) { // 2
				if(mp[one]==0)mp[one] = co ++;
				if(mp[two]==0)mp[two] = co++;
			} else { // 3
				swap(two,three);
				if(mp[one]==0)mp[one] = co ++;
				if(mp[two]==0)mp[two] = co ++;
				if(mp[three]==0)mp[three] = co ++;
			}
			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';
					tmp[mp[C[j.s].f/new_R]].pb(j);
			}
			// cerr << '\n' << '\n';
		}
	}
	R=new_R; latest = co-1;
			assert(co < MAXN);
	FOR(i,0,latest+1) ind[i]=tmp[i];
	// ll p = -LLINF;
	// FOR(i,1,latest+1) {
		// assert(ind[i].size());
		// ll hmm = C[ind[i][0].s].f/R;
		// for(auto j : ind[i]) if(hmm != C[j.s].f/R) assert(0);
		// assert(hmm >= p);
		// p = hmm;
	// }
}
void sdb 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||i>latest)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 << ' ';
}
/* for when u need negative numbers too */
inline int sdb ri() {
	bool neg = false;
	int res = 0;
	char c = getchar_unlocked();
	while (true) {
		if (c=='-') break;
		if ('0'<=c && c<='9') break;
		c = getchar_unlocked();
	}
	if (c=='-') neg = true;
	else res = c-'0';
	while (true) {
		c = getchar_unlocked();
		if (c<'0' || c>'9') break;
		res = (res<<1) + (res<<3) + (c-'0');
	}
	if (neg) return -res;
	return res;
}
void st3() {
	vector<ll>inter(n,0); vector<bool>re(n,0); set <pi> ms;
	vector <pi> events;
	FOR(i,0,n) events.pb(pi(C[i].s-A[i].f,i)), events.pb(pi(C[i].s+A[i].f,-i-1));
	sort(all(events), [] (pi x, pi y) { if(x.f != y.f) return x.f < y.f; else return x.s > y.s; } );
	for(auto j : events) {
		ll i = j.s;
		if(i>=0) { ll r = A[i].f; ll x = C[i].f;
			bool in = 1; pi near = pi(LLINF, LLINF);
			if(!ms.empty()) {
				// pi near = LLINF;
				auto itr = ms.lower_bound(pi(x,0));
				if(itr != ms.end()) near = min(near, pi(mdist(C[itr->s].f,C[itr->s].s, C[i].f, C[i].s)-(ld)A[itr->s].f, itr->s));
				if(itr != ms.begin()) { --itr; near = min(near, pi(mdist(C[itr->s].f,C[itr->s].s, C[i].f, C[i].s)-(ld)A[itr->s].f, itr->s)); }
			    assert(near.f != LLINF); 
				if(near.f-EPS <= (ld)r) in = 0;
			}
			if(in) {
				ms.ins(pi(x,i)); re[i] = 1;
			} else {
				re[i] = 0; assert(re[near.s]);
				assert((ms.find(pi(C[near.s].f, near.s))!=ms.end()));
				// assert(ms.find(pi(C[near.s].f+A[near.s].f, near.s))!=ms.end());
				ms.erase(ms.find(pi(C[near.s].f, near.s)));
				// ms.erase(ms.find(pi(C[near.s].f+A[near.s].f, near.s)));
				re[near.s] = 0;
				inter[i] = near.s;
				inter[near.s] = i;
			}
		} else {
			i = -i-1; if(re[i] == 0) continue;
			ll r = A[i].f; ll x = C[i].f;
			ms.erase(ms.find(pi(x,i)));
//  			bool in = 1; pi near = pi(LLINF, LLINF);
// 			if(!ms.empty()) {
// 				// pi near = LLINF;
// 				auto itr = ms.lower_bound(pi(x,0));
// 				if(itr != ms.end()) near = min(near, pi(mdist(C[itr->s].f,C[itr->s].s, C[i].f, C[i].s)-(ld)A[itr->s].f, itr->s));
// 				if(itr != ms.begin()) { --itr; near = min(near, pi(mdist(C[itr->s].f,C[itr->s].s, C[i].f, C[i].s)-(ld)A[itr->s].f, itr->s)); }
// 			    assert(near.f != LLINF); 
// 				if(near.f-EPS <= (ld)r) in = 0;
// 			}
// 			if(!in) {
// 				re[i] = 0; assert(re[near.s]);
// 				assert((ms.find(pi(C[near.s].f, near.s))!=ms.end()));
// 				// assert(ms.find(pi(C[near.s].f+A[near.s].f, near.s))!=ms.end());
// 				ms.erase(ms.find(pi(C[near.s].f, near.s)));
// 				// ms.erase(ms.find(pi(C[near.s].f+A[near.s].f, near.s)));
// 				re[near.s] = 0;
// 				inter[i] = near.s;
// 				inter[near.s] = i;
// 			}
            auto itr = ms.lower_bound(pi(x,0));
            if(itr != ms.end()) assert(itr->f > x);
            if(itr != ms.begin() && itr != ms.end()) {
                ll a = prev(itr)->s, b = itr->s;
                if(mdist(C[a].f,C[a].s,C[b].f,C[b].s) <= (ld)A[a].f + (ld)A[b].f){
                    re[a] = re[b] = 0;
                    inter[a] = b;
                    inter[b] = a;
                    itr=ms.erase(prev(itr));
                    ms.erase(itr);
                }
            }
		}
	}
	FOR(i,0,n) ans[i] = i;
	FOR(i,0,n) if(!re[i]&&(A[inter[i]].f>A[i].f||(A[inter[i]].f==A[i].f&&inter[i]<i))) { ans[i] = inter[i]; } 
	FOR(i,0,n) cout << ans[i]+1 << ' '; cout<<'\n';
}
int sdb main()
{
	// freopen("int","r",stdin); // freopen("out","w",stdout);
	FAST
	//cin >> n;
  n=ri();
	FOR(i,0,n) {
C[i].f=ri();C[i].s=ri();A[i].f=ri();//		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;
		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((ll)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());
	if(s4||n<=2e5||s2)st4();
	else st3();
}
// 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 (stderr)

circle_selection.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("Ofast")
 
circle_selection.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")
 
circle_selection.cpp: In function 'void st4()':
circle_selection.cpp:156:24: warning: unused variable 'y' [-Wunused-variable]
   ll x = mp[C[i].f/R], y = C[i].s;
                        ^
circle_selection.cpp: In function 'void st3()':
circle_selection.cpp:224:7: warning: unused variable 'r' [-Wunused-variable]
    ll r = A[i].f; ll x = C[i].f;
       ^
circle_selection.cpp:23:25: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 #define FOR(ii, ss, ee) for(ll ii = ss; ii < ee; ++ii)
                         ^
circle_selection.cpp:261:2: note: in expansion of macro 'FOR'
  FOR(i,0,n) cout << ans[i]+1 << ' '; cout<<'\n';
  ^~~
circle_selection.cpp:261:38: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  FOR(i,0,n) cout << ans[i]+1 << ' '; cout<<'\n';
                                      ^~~~

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 30 / 30
• Subtask 6: 0 / 13