oj.uz

Submission #111183

# Submission time Handle Problem Language Result Execution time Memory
111183 2019-05-14T03:10:05 Z oToToT Circle selection (APIO18_circle_selection) C++14
72 / 100
 3000 ms 307256 KB 
#pragma GCC optimize( "O3" )
#include <bits/stdc++.h>
using namespace std;
const int N = 300000 + 5;
const int C = 1000000000;
template < typename A, typename B >
using UMP = unordered_map< A, B >;
using lld = int64_t;

static inline int gc() {
  static char buf[1 << 20], *p = buf, *end = buf;
  if (p == end) {
    if ((end = buf + fread(buf, 1, 1 << 20, stdin)) == buf) return EOF;
    p = buf;
  }
  return *p++;
}
template<typename T>
static inline bool gn(T &_){
  register int c = gc(); register T __ = 1; _ = 0;
  while(!isdigit(c) and c!=EOF and c!='-') c = gc();
  if(c == '-') { __ = -1; c = gc(); }
  if(c == EOF) return false;
  while(isdigit(c)) _ = _ * 10 + c - '0', c = gc();
  _ *= __;
  return true;
}
template <typename T, typename ...Args>
static inline bool gn(T &x, Args& ...args){return gn(x) and gn(args...);}

int n;
vector< int > ord;
lld x[ N ], y[ N ], r[ N ];

inline bool inter( int i, int j ) {
	const lld ox = x[ i ] - x[ j ];
	const lld oy = y[ i ] - y[ j ];
	const lld R = r[ i ] + r[ j ];
	return ox * ox + oy * oy <= R * R;
}

void init() {
	gn( n );
	for ( int i = 0 ; i < n ; ++ i )
		gn( x[ i ], y[ i ], r[ i ] );
	for ( int i = 0 ; i < n ; ++ i )
		x[ i ] += C, y[ i ] += C;

	ord.resize( n );
	iota( ord.begin(), ord.end(), 0 );
	sort( ord.begin(), ord.end(), []( int a, int b ) {
		return tie( r[ a ], b ) > tie( r[ b ], a );
	} );
}

UMP< lld, UMP< lld, vector< int > > > plane;
int ans[ N ];
int LogL = 32;
lld unit = 1;
inline void build() {
	plane.clear(); plane.rehash( n * 10 );
	for ( int i = 0 ; i < n ; ++ i ) {
		if ( ans[ i ] ) continue;
		plane[ x[ i ] >> LogL ][ y[ i ] >> LogL ].push_back( i );
	}
}

const int dx[] = { -1, 0, 1 }, dy[] = { -1, 0, 1 };

void solve() {
	build();
	for ( int i : ord ) {
		if ( ans[ i ] ) continue;
		ans[ i ] = i + 1;
		int pLogL = LogL;
		while( ( unit << ( -- LogL ) ) > r[ i ] + r[ i ] );
		if ( pLogL != ++ LogL ) build();
		lld X = x[ i ] >> LogL, Y = y[ i ] >> LogL;
		for ( int i_ = 0 ; i_ < 3 ; ++ i_ ) {
			for ( int j_ = 0 ; j_ < 3 ; ++ j_ ) {
				for ( int j : plane[ X + dx[ i_ ] ][ Y + dy[ j_ ] ] ) {
					if ( ans[ j ] ) continue;
					if ( inter( i, j ) ) ans[ j ] = i + 1;
				}
			}
		}
	}
	for ( int i = 0 ; i < n ; ++ i )
		printf( "%d%c", ans[ i ], " \n"[ i == n - 1 ] );
}

int main() {
	init(); solve();
	return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 3 ms 512 KB Output is correct
17 Correct 2 ms 512 KB Output is correct
18 Correct 3 ms 512 KB Output is correct
19 Correct 6 ms 1152 KB Output is correct
20 Correct 4 ms 1152 KB Output is correct
21 Correct 7 ms 1152 KB Output is correct
22 Correct 19 ms 2688 KB Output is correct
23 Correct 21 ms 2560 KB Output is correct
24 Correct 21 ms 2560 KB Output is correct
25 Correct 17 ms 3456 KB Output is correct
26 Correct 18 ms 2944 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 39600 KB Output is correct
2 Correct 190 ms 40268 KB Output is correct
3 Correct 193 ms 40652 KB Output is correct
4 Correct 177 ms 38860 KB Output is correct
5 Correct 229 ms 39884 KB Output is correct
6 Correct 1197 ms 59420 KB Output is correct
7 Correct 341 ms 40896 KB Output is correct
8 Correct 514 ms 42772 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 1187 ms 39636 KB Output is correct
3 Execution timed out 3057 ms 110540 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2922 ms 209020 KB Output is correct
2 Correct 1992 ms 307256 KB Output is correct
3 Correct 210 ms 40848 KB Output is correct
4 Correct 1730 ms 259560 KB Output is correct
5 Correct 1492 ms 287168 KB Output is correct
6 Correct 250 ms 39376 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 3 ms 512 KB Output is correct
17 Correct 2 ms 512 KB Output is correct
18 Correct 3 ms 512 KB Output is correct
19 Correct 6 ms 1152 KB Output is correct
20 Correct 4 ms 1152 KB Output is correct
21 Correct 7 ms 1152 KB Output is correct
22 Correct 19 ms 2688 KB Output is correct
23 Correct 21 ms 2560 KB Output is correct
24 Correct 21 ms 2560 KB Output is correct
25 Correct 17 ms 3456 KB Output is correct
26 Correct 18 ms 2944 KB Output is correct
27 Correct 11 ms 2048 KB Output is correct
28 Correct 8 ms 1948 KB Output is correct
29 Correct 8 ms 2048 KB Output is correct
30 Correct 42 ms 5112 KB Output is correct
31 Correct 49 ms 5496 KB Output is correct
32 Correct 45 ms 4736 KB Output is correct
33 Correct 57 ms 14312 KB Output is correct
34 Correct 51 ms 14296 KB Output is correct
35 Correct 69 ms 13672 KB Output is correct
36 Correct 1086 ms 44776 KB Output is correct
37 Correct 970 ms 40912 KB Output is correct
38 Correct 1130 ms 44028 KB Output is correct
39 Correct 212 ms 15640 KB Output is correct
40 Correct 236 ms 15656 KB Output is correct
41 Correct 238 ms 15604 KB Output is correct
42 Correct 151 ms 15332 KB Output is correct
43 Correct 452 ms 89600 KB Output is correct
44 Correct 370 ms 89572 KB Output is correct
45 Correct 400 ms 89524 KB Output is correct
46 Correct 326 ms 89576 KB Output is correct
47 Correct 435 ms 89704 KB Output is correct
48 Correct 343 ms 89680 KB Output is correct
49 Correct 353 ms 89904 KB Output is correct
50 Correct 369 ms 89576 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 3 ms 512 KB Output is correct
17 Correct 2 ms 512 KB Output is correct
18 Correct 3 ms 512 KB Output is correct
19 Correct 6 ms 1152 KB Output is correct
20 Correct 4 ms 1152 KB Output is correct
21 Correct 7 ms 1152 KB Output is correct
22 Correct 19 ms 2688 KB Output is correct
23 Correct 21 ms 2560 KB Output is correct
24 Correct 21 ms 2560 KB Output is correct
25 Correct 17 ms 3456 KB Output is correct
26 Correct 18 ms 2944 KB Output is correct
27 Correct 168 ms 39600 KB Output is correct
28 Correct 190 ms 40268 KB Output is correct
29 Correct 193 ms 40652 KB Output is correct
30 Correct 177 ms 38860 KB Output is correct
31 Correct 229 ms 39884 KB Output is correct
32 Correct 1197 ms 59420 KB Output is correct
33 Correct 341 ms 40896 KB Output is correct
34 Correct 514 ms 42772 KB Output is correct
35 Correct 3 ms 384 KB Output is correct
36 Correct 1187 ms 39636 KB Output is correct
37 Execution timed out 3057 ms 110540 KB Time limit exceeded
38 Halted 0 ms 0 KB -