oj.uz

Submission #85000

# Submission time Handle Problem Language Result Execution time Memory
85000 2018-11-18T02:21:43 Z qkxwsm Circle selection (APIO18_circle_selection) C++14
100 / 100
 2176 ms 569896 KB 
/*
:>
*/
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/rope>

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

random_device(rd);
mt19937 rng(rd());
const long long FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();

struct custom_hash
{
	template<class T>
	unsigned long long operator()(T v) const
	{
		unsigned long long x = v;
		x += FIXED_RANDOM; x += 11400714819323198485ull;
		x = (x ^ (x >> 30)) * 13787848793156543929ull;
		x = (x ^ (x >> 27)) * 10723151780598845931ull;
		return x ^ (x >> 31);
	}
};

template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T, class U> using hash_table = gp_hash_table<T, U, custom_hash>;

template<class T>
void readi(T &x)
{
	x = 0;
	bool negative = false;
	char c = ' ';
	while (c < '-')
	{
		c = getchar();
	}
	if (c == '-')
	{
		negative = true;
		c = getchar();
	}
	while (c >= '0')
	{
		x = x * 10 + (c - '0');
		c = getchar();
	}
	if (negative)
	{
		x = -x;
	}
}
template<class T>
void printi(T output)
{
	if (output == 0)
	{
		putchar('0');
		return;
	}
	if (output < 0)
	{
		putchar('-');
		output = -output;
	}
	int buf[20], n = 0;
	while(output)
	{
		buf[n] = ((output % 10));
		output /= 10;
		n++;
	}
	for (n--; n >= 0; n--)
	{
		putchar(buf[n] + '0');
	}
	return;
}
template<class T>
void ckmin(T &a, T b)
{
	a = min(a, b);
}
template<class T>
void ckmax(T &a, T b)
{
	a = max(a, b);
}
long long expo(long long a, long long e, long long mod)
{
	return ((e == 0) ? 1 : ((expo(a * a % mod, e >> 1, mod)) * ((e & 1) ? a : 1) % mod));
}
template<class T, class U>
void nmod(T &x, U mod)
{
	if (x >= mod) x -= mod;
}
template<class T>
T gcd(T a, T b)
{
	return (b ? gcd(b, a % b) : a);
}
template<class T>
T randomize(T mod)
{
	return (uniform_int_distribution<T>(0, mod - 1))(rng);
}

#define y0 ___y0
#define y1 ___y1
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define PF push_front
#define fi first
#define se second
#define debug(x) cerr << #x << " = " << x << endl;
#define SZ(x) ((int) (x.size()))

const long double PI = 4.0 * atan(1.0);
const long double EPS = 1e-9;

#define MAGIC 347
#define SINF 10007
#define CO 1000007
#define INF 1000000007
#define BIG 1000000931
#define LARGE 1696969696967ll
#define GIANT 2564008813937411ll
#define LLINF 2696969696969696969ll
#define MAXN 300013

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;
typedef pair<pll, pll> ppp;

int N;
ppp arr[MAXN];
int ans[MAXN];

bool cmp(ppp a, ppp b)
{
	if (a.fi.fi != b.fi.fi)
	{
		return a.fi.fi > b.fi.fi;
	}
	return a.fi.se < b.fi.se;
}

ll dist(pll a, pll b)
{
	return (a.fi - b.fi) * (a.fi - b.fi) + (a.se - b.se) * (a.se - b.se);
}
bool intersect(ppp a, ppp b)
{
	return dist(a.se, b.se) <= (a.fi.fi + b.fi.fi) * (a.fi.fi + b.fi.fi);
}
hash_table<ll, vi> stor;

int32_t main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	// cout << fixed << setprecision(10);
	// cerr << fixed << setprecision(10);
	// freopen ("file.in", "r", stdin);
	// freopen ("file.out", "w", stdout);
	readi(N);
	for (int i = 0; i < N; i++)
	{
		readi(arr[i].se.fi); readi(arr[i].se.se); readi(arr[i].fi.fi); arr[i].fi.se = i;
		arr[i].se.fi += INF; arr[i].se.se += INF;
		ans[i] = -1;
	}
	sort(arr, arr + N, cmp);
	int iter = 0;
	for (int i = 32; i >= 2; i--)
	{
		//all circles of radius [2^i - 1...2^i)
		ll block = (1ll << i);
		if (arr[iter].fi.fi < block / 4) continue;
		stor.clear();
		for (int j = 0; j < N; j++)
		{
			if (ans[arr[j].fi.se] != -1) continue;
			ll x = arr[j].se.fi, y = arr[j].se.se;
			stor[(((x / block) * block) << 31) + ((y / block) * block)].PB(j);
		}
		while(iter < N && arr[iter].fi.fi >= (block / 4))
		{
			if (ans[arr[iter].fi.se] != -1)
			{
				iter++;
				continue;
			}
			ll bx = arr[iter].se.fi / block, by = arr[iter].se.se / block;
			for (int j = -1; j <= 1; j++)
			{
				for (int k = -1; k <= 1; k++)
				{
					vi v = stor[(((bx + j) * block) << 31) + ((by + k) * block)]; vi res;
					for (int idx : v)
					{
						if (intersect(arr[idx], arr[iter]))
						{
							ans[arr[idx].fi.se] = arr[iter].fi.se;
						}
						else
						{
							res.PB(idx);
						}
					}
					stor[(((bx + j) * block) << 31) + ((by + k) * block)] = res;
				}
			}
			iter++;
		}
	}
	for (int i = 0; i < N; i++)
	{
		ans[i]++;
		if (i) putchar(' ');
		printi(ans[i]);
	}
	putchar('\n');
	// cerr << "time elapsed = " << (clock() / (CLOCKS_PER_SEC / 1000)) << " ms" << endl;
	return 0;
}
/*
3
43731976 204781684 256609825
24705554 727971615 76690539
190036976 276041388 165781486
*/

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 408 KB Output is correct
4 Correct 2 ms 484 KB Output is correct
5 Correct 2 ms 560 KB Output is correct
6 Correct 2 ms 560 KB Output is correct
7 Correct 2 ms 560 KB Output is correct
8 Correct 2 ms 560 KB Output is correct
9 Correct 2 ms 560 KB Output is correct
10 Correct 2 ms 564 KB Output is correct
11 Correct 2 ms 688 KB Output is correct
12 Correct 2 ms 688 KB Output is correct
13 Correct 2 ms 688 KB Output is correct
14 Correct 2 ms 784 KB Output is correct
15 Correct 2 ms 784 KB Output is correct
16 Correct 2 ms 784 KB Output is correct
17 Correct 2 ms 784 KB Output is correct
18 Correct 2 ms 784 KB Output is correct
19 Correct 5 ms 892 KB Output is correct
20 Correct 5 ms 892 KB Output is correct
21 Correct 5 ms 908 KB Output is correct
22 Correct 19 ms 4896 KB Output is correct
23 Correct 31 ms 6300 KB Output is correct
24 Correct 22 ms 6564 KB Output is correct
25 Correct 21 ms 6564 KB Output is correct
26 Correct 22 ms 6564 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 14476 KB Output is correct
2 Correct 239 ms 14624 KB Output is correct
3 Correct 226 ms 14772 KB Output is correct
4 Correct 212 ms 14772 KB Output is correct
5 Correct 239 ms 15832 KB Output is correct
6 Correct 700 ms 57424 KB Output is correct
7 Correct 280 ms 57424 KB Output is correct
8 Correct 308 ms 57424 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 57424 KB Output is correct
2 Correct 539 ms 91380 KB Output is correct
3 Correct 1950 ms 275484 KB Output is correct
4 Correct 1971 ms 275484 KB Output is correct
5 Correct 1621 ms 275484 KB Output is correct
6 Correct 713 ms 275484 KB Output is correct
7 Correct 339 ms 275484 KB Output is correct
8 Correct 42 ms 275484 KB Output is correct
9 Correct 1903 ms 275484 KB Output is correct
10 Correct 1340 ms 275484 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1850 ms 523768 KB Output is correct
2 Correct 1838 ms 523768 KB Output is correct
3 Correct 281 ms 523768 KB Output is correct
4 Correct 1892 ms 531184 KB Output is correct
5 Correct 1848 ms 538808 KB Output is correct
6 Correct 223 ms 538808 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 408 KB Output is correct
4 Correct 2 ms 484 KB Output is correct
5 Correct 2 ms 560 KB Output is correct
6 Correct 2 ms 560 KB Output is correct
7 Correct 2 ms 560 KB Output is correct
8 Correct 2 ms 560 KB Output is correct
9 Correct 2 ms 560 KB Output is correct
10 Correct 2 ms 564 KB Output is correct
11 Correct 2 ms 688 KB Output is correct
12 Correct 2 ms 688 KB Output is correct
13 Correct 2 ms 688 KB Output is correct
14 Correct 2 ms 784 KB Output is correct
15 Correct 2 ms 784 KB Output is correct
16 Correct 2 ms 784 KB Output is correct
17 Correct 2 ms 784 KB Output is correct
18 Correct 2 ms 784 KB Output is correct
19 Correct 5 ms 892 KB Output is correct
20 Correct 5 ms 892 KB Output is correct
21 Correct 5 ms 908 KB Output is correct
22 Correct 19 ms 4896 KB Output is correct
23 Correct 31 ms 6300 KB Output is correct
24 Correct 22 ms 6564 KB Output is correct
25 Correct 21 ms 6564 KB Output is correct
26 Correct 22 ms 6564 KB Output is correct
27 Correct 9 ms 538808 KB Output is correct
28 Correct 9 ms 538808 KB Output is correct
29 Correct 11 ms 538808 KB Output is correct
30 Correct 40 ms 538808 KB Output is correct
31 Correct 41 ms 538808 KB Output is correct
32 Correct 48 ms 538808 KB Output is correct
33 Correct 77 ms 538808 KB Output is correct
34 Correct 99 ms 538808 KB Output is correct
35 Correct 83 ms 538808 KB Output is correct
36 Correct 531 ms 538808 KB Output is correct
37 Correct 618 ms 538808 KB Output is correct
38 Correct 563 ms 538808 KB Output is correct
39 Correct 301 ms 538808 KB Output is correct
40 Correct 286 ms 538808 KB Output is correct
41 Correct 312 ms 538808 KB Output is correct
42 Correct 98 ms 538808 KB Output is correct
43 Correct 519 ms 538808 KB Output is correct
44 Correct 509 ms 538808 KB Output is correct
45 Correct 543 ms 538808 KB Output is correct
46 Correct 569 ms 538808 KB Output is correct
47 Correct 528 ms 538808 KB Output is correct
48 Correct 517 ms 538808 KB Output is correct
49 Correct 508 ms 538808 KB Output is correct
50 Correct 497 ms 538808 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 408 KB Output is correct
4 Correct 2 ms 484 KB Output is correct
5 Correct 2 ms 560 KB Output is correct
6 Correct 2 ms 560 KB Output is correct
7 Correct 2 ms 560 KB Output is correct
8 Correct 2 ms 560 KB Output is correct
9 Correct 2 ms 560 KB Output is correct
10 Correct 2 ms 564 KB Output is correct
11 Correct 2 ms 688 KB Output is correct
12 Correct 2 ms 688 KB Output is correct
13 Correct 2 ms 688 KB Output is correct
14 Correct 2 ms 784 KB Output is correct
15 Correct 2 ms 784 KB Output is correct
16 Correct 2 ms 784 KB Output is correct
17 Correct 2 ms 784 KB Output is correct
18 Correct 2 ms 784 KB Output is correct
19 Correct 5 ms 892 KB Output is correct
20 Correct 5 ms 892 KB Output is correct
21 Correct 5 ms 908 KB Output is correct
22 Correct 19 ms 4896 KB Output is correct
23 Correct 31 ms 6300 KB Output is correct
24 Correct 22 ms 6564 KB Output is correct
25 Correct 21 ms 6564 KB Output is correct
26 Correct 22 ms 6564 KB Output is correct
27 Correct 215 ms 14476 KB Output is correct
28 Correct 239 ms 14624 KB Output is correct
29 Correct 226 ms 14772 KB Output is correct
30 Correct 212 ms 14772 KB Output is correct
31 Correct 239 ms 15832 KB Output is correct
32 Correct 700 ms 57424 KB Output is correct
33 Correct 280 ms 57424 KB Output is correct
34 Correct 308 ms 57424 KB Output is correct
35 Correct 2 ms 57424 KB Output is correct
36 Correct 539 ms 91380 KB Output is correct
37 Correct 1950 ms 275484 KB Output is correct
38 Correct 1971 ms 275484 KB Output is correct
39 Correct 1621 ms 275484 KB Output is correct
40 Correct 713 ms 275484 KB Output is correct
41 Correct 339 ms 275484 KB Output is correct
42 Correct 42 ms 275484 KB Output is correct
43 Correct 1903 ms 275484 KB Output is correct
44 Correct 1340 ms 275484 KB Output is correct
45 Correct 1850 ms 523768 KB Output is correct
46 Correct 1838 ms 523768 KB Output is correct
47 Correct 281 ms 523768 KB Output is correct
48 Correct 1892 ms 531184 KB Output is correct
49 Correct 1848 ms 538808 KB Output is correct
50 Correct 223 ms 538808 KB Output is correct
51 Correct 9 ms 538808 KB Output is correct
52 Correct 9 ms 538808 KB Output is correct
53 Correct 11 ms 538808 KB Output is correct
54 Correct 40 ms 538808 KB Output is correct
55 Correct 41 ms 538808 KB Output is correct
56 Correct 48 ms 538808 KB Output is correct
57 Correct 77 ms 538808 KB Output is correct
58 Correct 99 ms 538808 KB Output is correct
59 Correct 83 ms 538808 KB Output is correct
60 Correct 531 ms 538808 KB Output is correct
61 Correct 618 ms 538808 KB Output is correct
62 Correct 563 ms 538808 KB Output is correct
63 Correct 301 ms 538808 KB Output is correct
64 Correct 286 ms 538808 KB Output is correct
65 Correct 312 ms 538808 KB Output is correct
66 Correct 98 ms 538808 KB Output is correct
67 Correct 519 ms 538808 KB Output is correct
68 Correct 509 ms 538808 KB Output is correct
69 Correct 543 ms 538808 KB Output is correct
70 Correct 569 ms 538808 KB Output is correct
71 Correct 528 ms 538808 KB Output is correct
72 Correct 517 ms 538808 KB Output is correct
73 Correct 508 ms 538808 KB Output is correct
74 Correct 497 ms 538808 KB Output is correct
75 Correct 226 ms 538808 KB Output is correct
76 Correct 224 ms 538808 KB Output is correct
77 Correct 239 ms 538808 KB Output is correct
78 Correct 238 ms 538808 KB Output is correct
79 Correct 263 ms 538808 KB Output is correct
80 Correct 229 ms 538808 KB Output is correct
81 Correct 2091 ms 538808 KB Output is correct
82 Correct 1926 ms 538808 KB Output is correct
83 Correct 1734 ms 538808 KB Output is correct
84 Correct 1958 ms 538808 KB Output is correct
85 Correct 1918 ms 538808 KB Output is correct
86 Correct 1902 ms 538808 KB Output is correct
87 Correct 1682 ms 538808 KB Output is correct
88 Correct 955 ms 538808 KB Output is correct
89 Correct 996 ms 538808 KB Output is correct
90 Correct 1008 ms 538808 KB Output is correct
91 Correct 964 ms 538808 KB Output is correct
92 Correct 925 ms 538808 KB Output is correct
93 Correct 2125 ms 538808 KB Output is correct
94 Correct 2008 ms 538808 KB Output is correct
95 Correct 2176 ms 538808 KB Output is correct
96 Correct 2064 ms 538808 KB Output is correct
97 Correct 1870 ms 538808 KB Output is correct
98 Correct 704 ms 538808 KB Output is correct
99 Correct 1905 ms 538808 KB Output is correct
100 Correct 1999 ms 538808 KB Output is correct
101 Correct 882 ms 538808 KB Output is correct
102 Correct 1844 ms 538808 KB Output is correct
103 Correct 2059 ms 538808 KB Output is correct
104 Correct 1847 ms 538808 KB Output is correct
105 Correct 434 ms 538808 KB Output is correct
106 Correct 1295 ms 538808 KB Output is correct
107 Correct 1218 ms 538808 KB Output is correct
108 Correct 1218 ms 538948 KB Output is correct
109 Correct 1214 ms 546852 KB Output is correct
110 Correct 1302 ms 547120 KB Output is correct
111 Correct 1262 ms 547120 KB Output is correct
112 Correct 1231 ms 547128 KB Output is correct
113 Correct 1362 ms 547128 KB Output is correct
114 Correct 1307 ms 554240 KB Output is correct
115 Correct 1302 ms 562248 KB Output is correct
116 Correct 1277 ms 569896 KB Output is correct