oj.uz

Submission #624105

# Submission time Handle Problem Language Result Execution time Memory
624105 2022-08-07T09:10:52 Z Arnch Circle selection (APIO18_circle_selection) C++17
0 / 100
 241 ms 35940 KB 
// oooo
/*
 har chi delet mikhad bebar ~
 gitar o ba khodet nabar! ~
 ;Amoo_Hasan;
*/

#include<bits/stdc++.h>
//#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
//#pragma GCC target("avx2,fma")

using namespace std;

typedef long long ll;
typedef long double ld;

#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
#define wtf(x) cout<<#x <<" : " <<x <<endl

constexpr ll inf = 1e18, N = 1e6 + 10, mod = 1e9 + 7, pr = 1000696969;

int x[N], y[N], rad[N], ans[N], l[N], r[N];
bool mark[N];
vector<int> adj[N], vc, po;

bool Ok(int i, int j) {
	ll cur = 1ll * (x[i] - x[j]) * (x[i] - x[j]);
	cur += 1ll * (y[i] - y[j]) * (y[i] - y[j]);

	if(cur <= 1ll * (rad[i] + rad[j]) * (rad[i] + rad[j])) return true;
	return false;
}
bool cmp(int i, int j) {
	return x[i] > x[j];
}
bool cmp2(int i, int j) {
	if(rad[vc[i]] != rad[vc[j]])
		return rad[vc[i]] < rad[vc[j]];
	return vc[i] > vc[j];
}

int main() {
    ios :: sync_with_stdio(0), cin.tie(0);

	int n; cin >>n;
	for(int i = 0; i < n; i++) cin >>x[i] >>y[i] >>rad[i];

	for(int i = 0; i < n; i++) vc.push_back(i), po.push_back(i);
	sort(All(vc), cmp), sort(All(po), cmp2);

	for(int i = 0; i < Sz(vc); i++) {
		l[i] = i - 1, r[i] = i + 1;
	}

	int tim = n;
	while(tim--) {
		int pos = po.back(); po.pop_back();
		if(mark[vc[pos]]) continue;
		mark[vc[pos]] = 1, ans[vc[pos]] = vc[pos];
		int ind = pos;
		pos = l[ind];
		while(pos != -1 && Ok(vc[pos], vc[ind])) {
			mark[vc[pos]] = 1;
			ans[vc[pos]] = vc[ind];
			int nxt = l[pos];
			r[l[pos]] = ind, l[ind] = l[pos];
			pos = nxt;
		}
		pos = r[ind];
		while(pos != n && Ok(vc[pos], vc[ind])) {
			mark[vc[pos]] = 1;
			ans[vc[pos]] = vc[ind];
			int nxt = r[pos];
			l[r[pos]] = ind, r[ind] = r[pos];
			pos = nxt;
		}
	}

	for(int i = 0; i < n; i++) cout<<ans[i] + 1 <<' ';

    return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 13 ms 23848 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 13 ms 23824 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 13 ms 23864 KB Output is correct
7 Correct 13 ms 23852 KB Output is correct
8 Incorrect 15 ms 23752 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 221 ms 35940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 23780 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 241 ms 35756 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 13 ms 23848 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 13 ms 23824 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 13 ms 23864 KB Output is correct
7 Correct 13 ms 23852 KB Output is correct
8 Incorrect 15 ms 23752 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 13 ms 23848 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 13 ms 23824 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 13 ms 23864 KB Output is correct
7 Correct 13 ms 23852 KB Output is correct
8 Incorrect 15 ms 23752 KB Output isn't correct
9 Halted 0 ms 0 KB -