oj.uz

답안 #109044

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
109044 2019-05-04T06:04:56 Z ryansee 원 고르기 (APIO18_circle_selection) C++14
0 / 100
 9 ms 2176 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 5100//(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)) ); }
string st1() {
	sort(A,A+n, [] (pi x, pi y) { if(x.f!=y.f) return x.f > y.f; else return x.s < y.s; } );
	FOR(ii,0,n) {
		ll i = A[ii].s;
		ll r = A[ii].f; 
		if(done[i]) continue;
		ans[i] = i;
		FOR(j,ii+1,n) {
			if(!done[A[j].s] && mdist(C[i].f,C[i].s,C[A[j].s].f,C[A[j].s].s) <= (ld)r + (ld)A[j].f) {
				done[A[j].s] = 1;
				ans[A[j].s] = i;
			}
		}
	}
	FOR(i,0,n) cout << ans[i] + 1 << ' '; cout << '\n';
	string s = ""; FOR(i,0,n) s += to_string(ans[i]+1); return s;
}
string st2() {
	sort(A,A+n, [] (pi x, pi y) { if(x.f!=y.f) return x.f > y.f; else return x.s < y.s; } );
	mmst(ans,0);
	multiset <pi> ms_smol,ms_big; // x-coord, radius, index
	FOR(i,0,n) {
		ms_smol.ins(pi(C[A[i].s].f+A[i].f, i));
		ms_big.ins(pi(C[A[i].s].f-A[i].f, i));
	}
	FOR(i,0,n) {
		if(ms_smol.find(pi(C[A[i].s].f+A[i].f, i)) == ms_smol.end()) { continue; }
		while(1) {
			auto itrrr = ms_big.find(pi(C[A[i].s].f-A[i].f, i));
			auto itr2 = next(itrrr);
			if(itr2==ms_big.end()) break;
			if(C[A[i].s].f + A[i].f >= itr2->f) { ans[A[itr2->s].s] = A[i].s; ms_smol.erase(ms_smol.find(pi(C[A[itr2->s].s].f+A[itr2->s].f, itr2->s))); ms_big.erase(itr2); }
			else break;
		}
		while(1) {
			auto itrrr = ms_smol.find(pi(C[A[i].s].f+A[i].f, i)); if(itrrr==ms_smol.begin()) break;
			auto itr2 = prev(itrrr);
			if(C[A[i].s].f - A[i].f <= itr2->f) { ans[A[itr2->s].s] = A[i].s; ms_smol.erase(itr2); ms_big.erase(ms_big.find(pi(C[A[itr2->s].s].f-A[itr2->s].f, itr2->s))); }
			else break;
		}
		ms_smol.erase(ms_smol.find(pi(C[A[i].s].f+A[i].f,i)));
		ms_big.erase(ms_big.find(pi(C[A[i].s].f-A[i].f,i)));
		ans[A[i].s] = A[i].s;
	}
	FOR(i,0,n) cout << ans[i]+1 << ' '; cout << '\n';
	string s = ""; FOR(i,0,n) s += to_string(ans[i]+1); return s;
}
// ll mdist(ll a, ll b, ll c, ll d) { return llabs(a-c)+llabs(b-d); }
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';
}
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);
			// cerr << one << ' ' << two << '\n';
			for(auto j : ind[i]) {
				// cerr << C[j.s].f << ' ' << new_R << ' ' << C[j.s].f/new_R << '\n';
				if(C[j.s].f/new_R == one) { mp[C[j.s].f/new_R] = co; tmp[co].pb(j); }
				else if(C[j.s].f/new_R == two) { mp[C[j.s].f/new_R] = co + 1; tmp[co+1].pb(j); }
				else assert(0);
			}
			// cerr << '\n' << '\n';
			co += 2;
		}
	}
	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));
		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());
	if(n <= 5000&&0) {
		st1();
	} else if(s2&&0) {
		st2();
	} else if(s4||1) { // becos i edited editorial solution here (the AC solution)
		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

circle_selection.cpp: In function 'std::__cxx11::string st1()':
circle_selection.cpp:19: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:55:2: note: in expansion of macro 'FOR'
  FOR(i,0,n) cout << ans[i] + 1 << ' '; cout << '\n';
  ^~~
circle_selection.cpp:55:40: 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';
                                        ^~~~
circle_selection.cpp: In function 'std::__cxx11::string st2()':
circle_selection.cpp:19: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:85:2: note: in expansion of macro 'FOR'
  FOR(i,0,n) cout << ans[i]+1 << ' '; cout << '\n';
  ^~~
circle_selection.cpp:85: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';
                                      ^~~~
circle_selection.cpp: In function 'void st3()':
circle_selection.cpp:120:7: warning: unused variable 'r' [-Wunused-variable]
    ll r = A[i].f; ll x = C[i].f;
       ^
circle_selection.cpp:19: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:157:2: note: in expansion of macro 'FOR'
  FOR(i,0,n) cout << ans[i]+1 << ' '; cout<<'\n';
  ^~~
circle_selection.cpp:157: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';
                                      ^~~~
circle_selection.cpp: In function 'void st4()':
circle_selection.cpp:226:24: warning: unused variable 'y' [-Wunused-variable]
   ll x = mp[C[i].f/R], y = C[i].s;
                        ^

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 3 ms 640 KB Output is correct
5 Correct 3 ms 640 KB Output is correct
6 Correct 3 ms 640 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 2 ms 640 KB Output is correct
9 Correct 2 ms 640 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 3 ms 640 KB Output is correct
12 Correct 3 ms 640 KB Output is correct
13 Correct 3 ms 640 KB Output is correct
14 Correct 2 ms 640 KB Output is correct
15 Correct 3 ms 640 KB Output is correct
16 Correct 4 ms 768 KB Output is correct
17 Correct 3 ms 612 KB Output is correct
18 Correct 3 ms 740 KB Output is correct
19 Correct 7 ms 1024 KB Output is correct
20 Correct 6 ms 1024 KB Output is correct
21 Correct 8 ms 1408 KB Output is correct
22 Runtime error 9 ms 2020 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 1408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 9 ms 2176 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 3 ms 640 KB Output is correct
5 Correct 3 ms 640 KB Output is correct
6 Correct 3 ms 640 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 2 ms 640 KB Output is correct
9 Correct 2 ms 640 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 3 ms 640 KB Output is correct
12 Correct 3 ms 640 KB Output is correct
13 Correct 3 ms 640 KB Output is correct
14 Correct 2 ms 640 KB Output is correct
15 Correct 3 ms 640 KB Output is correct
16 Correct 4 ms 768 KB Output is correct
17 Correct 3 ms 612 KB Output is correct
18 Correct 3 ms 740 KB Output is correct
19 Correct 7 ms 1024 KB Output is correct
20 Correct 6 ms 1024 KB Output is correct
21 Correct 8 ms 1408 KB Output is correct
22 Runtime error 9 ms 2020 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 3 ms 640 KB Output is correct
5 Correct 3 ms 640 KB Output is correct
6 Correct 3 ms 640 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 2 ms 640 KB Output is correct
9 Correct 2 ms 640 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 3 ms 640 KB Output is correct
12 Correct 3 ms 640 KB Output is correct
13 Correct 3 ms 640 KB Output is correct
14 Correct 2 ms 640 KB Output is correct
15 Correct 3 ms 640 KB Output is correct
16 Correct 4 ms 768 KB Output is correct
17 Correct 3 ms 612 KB Output is correct
18 Correct 3 ms 740 KB Output is correct
19 Correct 7 ms 1024 KB Output is correct
20 Correct 6 ms 1024 KB Output is correct
21 Correct 8 ms 1408 KB Output is correct
22 Runtime error 9 ms 2020 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Halted 0 ms 0 KB -