oj.uz

답안 #533401

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
533401 2022-03-05T21:41:11 Z flappybird 원 고르기 (APIO18_circle_selection) C++14
0 / 100
 1460 ms 245212 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O0")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pi;
#define MAX 301010
#define MAXS 20
#define INF 1000000010
#define bb ' '
#define ln '\n'
#define Ln '\n'
pair<pi, pi> in[MAX];
int X[MAX];
int Y[MAX];
int R[MAX];
int ind[MAX];
int ri[MAX];
int ans[MAX];
ll sq(ll x) {
	return x * x;
}
inline bool chk(int i, int j) {
	return sq(X[i] - X[j]) + sq(Y[i] - Y[j]) <= sq(R[i] + R[j]);
}
bool isrange(int x, int y) {
	if (x < 0 || y < 0) return false;
	return true;
}
inline ll trans(int x, int y) {
	return ((ll)x * (ll)INF) + y;
}
bool cmp(pair<pi, pi>& p1, pair<pi, pi>& p2) {
	if (p1.first.first == p2.first.first) return p1.first.second < p2.first.second;
	else return p1.first.first > p2.first.first;
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N;
	cin >> N;
	int i;
	for (i = 1; i <= N; i++) cin >> in[i].second.first >> in[i].second.second >> in[i].first.first, in[i].first.second = i;
	sort(in + 1, in + N + 1, cmp);
	for (i = 1; i <= N; i++) tie(X[i], Y[i], R[i], ind[i]) = make_tuple(in[i].second.first + INF, in[i].second.second + INF, in[i].first.first, in[i].first.second);
	int k;
	int s, e;
	e = 0;
	for (k = 30; k >= 0; k--) {
		int r = 1 << k;
		s = e + 1;
		if (R[s] < r) continue;
		unordered_map<ll, vector<int>> mp;
		e = 0;
		for (i = s; i <= N; i++) {
			if (ans[i]) continue;
			int x, y;
			x = X[i] / r;
			y = Y[i] / r;
			if (R[i] < r && !e) e = i - 1;
			int xx, yy;
			if (R[i] <= r) {
				for (xx = x - 1; xx <= x + 1; xx++) for (yy = y - 1; yy <= y + 1; yy++) mp[((ll)xx * (ll)INF) + yy].push_back(i);
			}
			else {
				for (xx = x - 2; xx <= x + 2; xx += 2) for (yy = y - 2; yy <= y + 2; yy += 2) mp[((ll)xx * (ll)INF) + yy].push_back(i);
			}
		}
		if (e == 0) e = N;
		for (i = s; i <= e; i++) {
			if (ans[i]) continue;
			ans[i] = i;
			int x, y;
			x = X[i] / r;
			y = Y[i] / r;
			int xx, yy;
			if (R[i] <= r) {
				for (xx = x - 1; xx <= x + 1; xx++) for (yy = y - 1; yy <= y + 1; yy++) {
					ll t = ((ll)xx * (ll)INF) + yy;
					for (auto c : mp[t]) if (!ans[c] && chk(c, i)) ans[c] = i;
				}
			}
			else {
				for (xx = x - 2; xx <= x + 2; xx += 2) for (yy = y - 2; yy <= y + 2; yy += 2) {
					ll t = ((ll)xx * (ll)INF) + yy;
					for (auto c : mp[t]) if (!ans[c] && chk(c, i)) ans[c] = i;
				}
			}
		}
	}
	for (i = 1; i <= N; i++) ri[ind[i]] = i;
	for (i = 1; i <= N; i++) cout << ind[ans[ri[i]]] << bb;
}

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Incorrect 0 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 206 ms 22848 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1371 ms 86120 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1460 ms 245212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Incorrect 0 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Incorrect 0 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -