oj.uz

답안 #1070996

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1070996 2024-08-22T22:42:37 Z pawned 원 고르기 (APIO18_circle_selection) C++17
23 / 100
 1679 ms 331600 KB 
#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;

const char nl = '\n';

void fastIO() {
	ios::sync_with_stdio(false);
	cin.tie(0);
}

ll dirX[9] = {-1, -1, -1, 0, 0, 0, 1, 1, 1};
ll dirY[9] = {-1, 0, 1, -1, 0, 1, -1, 0, 1};

ll N, R;

ll flat(ll x, ll y) {
	if (x >= 0)
		return x / y;
	else
		return -((-x + y - 1) / y);
}

bool intersect(ii c1, ii c2) {
	ll dx = abs(c1.fi - c2.fi);
	ll dy = abs(c1.se - c2.se);
	if (dx * dx + dy * dy <= 4 * R * R)
		return true;
	return false;
}

int main() {
	fastIO();
	ll N;
	cin>>N;
	vector<ii> cr(N);
	// {{x, y}, r}
	for (int i = 0; i < N; i++) {
		cin>>cr[i].fi>>cr[i].se;
		cin>>R;
	}
//	cout<<"R: "<<R<<endl;
	vector<ii> ft(N);
	map<ii, set<ll>> all;
	for (int i = 0; i < N; i++) {
		ft[i] = {flat(cr[i].fi, 2 * R), flat(cr[i].se, 2 * R)};
		all[ft[i]].insert(i);
	}
	vector<bool> vis(N, false);
	vi par(N, -1);
	for (int i = 0; i < N; i++) {
		if (vis[i])
			continue;
		ll xc = ft[i].fi;
		ll yc = ft[i].se;
		for (int j = 0; j < 9; j++) {
			ll xn = xc + dirX[j];
			ll yn = yc + dirY[j];
			vi toerase;
			for (int x : all[{xn, yn}]) {
				if (!vis[x] && intersect(cr[i], cr[x])) {
					vis[x] = true;
					par[x] = i;
					toerase.pb(x);
				}
			}
			for (int x : toerase)
				all[{xn, yn}].erase(x);
		}
	}
//	cout<<"ANSWER: ";
	for (int x : par)
		cout<<(x + 1)<<" ";
	cout<<endl;
}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 15.0

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

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1679 ms 323920 KB Output is correct
2 Correct 1335 ms 324180 KB Output is correct
3 Correct 299 ms 30408 KB Output is correct
4 Correct 1401 ms 331404 KB Output is correct
5 Correct 1324 ms 331600 KB Output is correct
6 Correct 286 ms 36436 KB Output is correct

Subtask #5
0 / 30.0

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

Subtask #6
0 / 13.0

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