oj.uz

Submission #543128

# Submission time Handle Problem Language Result Execution time Memory
543128 2022-03-29T11:42:12 Z square1001 Road Construction (JOI21_road_construction) C++14
100 / 100
 222 ms 20740 KB 
#include <set>
#include <cmath>
#include <cstdio>
#include <cstdint>
#include <algorithm>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
using namespace std;

uint64_t seed = 987654321;
uint64_t xorshift64() {
	seed ^= seed << 13;
	seed ^= seed >> 17;
	seed ^= seed << 7;
	return seed;
}
int rand_int(int l, int r) {
	return l + int(xorshift64() % (r - l));
}
int inv_binomial(int N, double p, double alpha) {
	// least N such that P(x <= N) >= alpha
	const double log_p1 = log(p);
	const double log_p2 = log(1.0 - p);
	double sum = 0.0;
	double logval = log_p2 * N;
	for (int i = 0; i < N; i++) {
		sum += exp(logval);
		if (sum >= alpha) {
			return i;
		}
		logval += log_p1 - log_p2 + log(double(N - i) / (i + 1));
	}
	return N;
}

int X[262144], Y[262144], A[262144], B[262144], perm[262144], permtmp[262144], cnt[66560];
unsigned dist[2097152], res[786432], restmp[786432];

int readint() {
	char ch = getchar_unlocked();
	bool minus = false;
	if (ch == '-') {
		minus = true;
		ch = getchar_unlocked();
	}
	int res = 0;
	while ('0' <= ch && ch <= '9') {
		res = res * 10 + int(ch - '0');
		ch = getchar_unlocked();
	}
	return (minus ? -res : res);
}

char buf[64];
void writeint(unsigned x) {
	int pos = 0;
	while (x > 0) {
		buf[pos++] = x % 10 + '0';
		x /= 10;
	}
	while (pos--) {
		putchar_unlocked(buf[pos]);
	}
	putchar_unlocked('\n');
}

int main() {
	// step #1. read input
	int N = readint();
	int K = readint();
	for (int i = 0; i < N; i++) {
		X[i] = readint();
		Y[i] = readint();
	}
	
	// step #2. random sampling setup
	const double p = double(K) / (1LL * N * (N - 1) / 2);
	const int samples = 2000000;
	const int rank = (p != 1.0 ? inv_binomial(samples, p, 0.95) : samples);
	
	// step #3. random sampling
	long long border;
	if (rank == samples) {
		border = (1LL << 32);
	}
	else {
		for (int i = 0; i < samples; i++) {
			int va = rand_int(0, N);
			int vb = (va + rand_int(1, N)) % N;
			dist[i] = abs(X[va] - X[vb]) + abs(Y[va] - Y[vb]);
		}
		nth_element(dist, dist + rank, dist + samples);
		border = dist[rank] - 1;
	}
	
	// step #4. rotate 45 degrees
	for (int i = 0; i < N; i++) {
		A[i] = X[i] + Y[i];
		B[i] = X[i] - Y[i];
	}
	
	// step #5. sort by A[i]
	for (int i = 0; i < N; i++) cnt[(A[i] & 65535) + 1]++;
	for (int i = 0; i < 65536; i++) cnt[i + 1] += cnt[i];
	for (int i = 0; i < N; i++) permtmp[cnt[A[i] & 65535]++] = i;
	for (int i = 0; i < 65537; i++) cnt[i] = 0;
	for (int i = 0; i < N; i++) cnt[(A[i] >> 16) + 32769]++;
	for (int i = 0; i < 65536; i++) cnt[i + 1] += cnt[i];
	for (int i = 0; i < N; i++) perm[cnt[(A[permtmp[i]] >> 16) + 32768]++] = permtmp[i];
	
	// step #6. sweepline algorithm
	int C = 0, pl = 0;
	set<pair<int, int> > s;
	for (int i = 0; i < N; i++) {
		int u = perm[i];
		int BL = max(B[u] - border, -2000000000LL);
		int BR = min(B[u] + border, +2000000000LL);
		while (A[u] - A[perm[pl]] > border) {
			s.erase(make_pair(B[perm[pl]], perm[pl]));
			pl++;
		}
		set<pair<int, int> >::iterator it = s.lower_bound(make_pair(BL, -1));
		while (it != s.end() && it->first <= BR) {
			res[C++] = abs(X[it->second] - X[u]) + abs(Y[it->second] - Y[u]);
			it++;
		}
		s.insert(make_pair(B[u], u));
	}
	
	// step #7. sort the distance
	for (int i = 0; i < 65537; i++) cnt[i] = 0;
	for (int i = 0; i < C; i++) cnt[(res[i] & 65535) + 1]++;
	for (int i = 0; i < 65536; i++) cnt[i + 1] += cnt[i];
	for (int i = 0; i < C; i++) restmp[cnt[res[i] & 65535]++] = res[i];
	for (int i = 0; i < 65537; i++) cnt[i] = 0;
	for (int i = 0; i < C; i++) cnt[(res[i] >> 16) + 1U]++;
	for (int i = 0; i < 65536; i++) cnt[i + 1] += cnt[i];
	for (int i = 0; i < C; i++) res[cnt[restmp[i] >> 16]++] = restmp[i];
	
	// step #8. final answer
	for (int i = 0; i < K; i++) {
		writeint(i < C ? res[i] : border + 1);
	}
	
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 12960 KB Output is correct
2 Correct 138 ms 12892 KB Output is correct
3 Correct 25 ms 5204 KB Output is correct
4 Correct 25 ms 5256 KB Output is correct
5 Correct 129 ms 11776 KB Output is correct
6 Correct 74 ms 8384 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 19428 KB Output is correct
2 Correct 146 ms 18252 KB Output is correct
3 Correct 23 ms 5000 KB Output is correct
4 Correct 133 ms 17996 KB Output is correct
5 Correct 114 ms 17416 KB Output is correct
6 Correct 125 ms 17424 KB Output is correct
7 Correct 116 ms 17304 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 14276 KB Output is correct
2 Correct 176 ms 14432 KB Output is correct
3 Correct 1 ms 720 KB Output is correct
4 Correct 112 ms 14156 KB Output is correct
5 Correct 172 ms 14180 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 14276 KB Output is correct
2 Correct 176 ms 14432 KB Output is correct
3 Correct 1 ms 720 KB Output is correct
4 Correct 112 ms 14156 KB Output is correct
5 Correct 172 ms 14180 KB Output is correct
6 Correct 159 ms 14276 KB Output is correct
7 Correct 164 ms 14404 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 171 ms 14304 KB Output is correct
11 Correct 107 ms 14284 KB Output is correct
12 Correct 163 ms 14284 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 12960 KB Output is correct
2 Correct 138 ms 12892 KB Output is correct
3 Correct 25 ms 5204 KB Output is correct
4 Correct 25 ms 5256 KB Output is correct
5 Correct 129 ms 11776 KB Output is correct
6 Correct 74 ms 8384 KB Output is correct
7 Correct 145 ms 14736 KB Output is correct
8 Correct 137 ms 15436 KB Output is correct
9 Correct 25 ms 5128 KB Output is correct
10 Correct 137 ms 14524 KB Output is correct
11 Correct 114 ms 14028 KB Output is correct
12 Correct 127 ms 12652 KB Output is correct
13 Correct 132 ms 13412 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 12960 KB Output is correct
2 Correct 138 ms 12892 KB Output is correct
3 Correct 25 ms 5204 KB Output is correct
4 Correct 25 ms 5256 KB Output is correct
5 Correct 129 ms 11776 KB Output is correct
6 Correct 74 ms 8384 KB Output is correct
7 Correct 142 ms 19428 KB Output is correct
8 Correct 146 ms 18252 KB Output is correct
9 Correct 23 ms 5000 KB Output is correct
10 Correct 133 ms 17996 KB Output is correct
11 Correct 114 ms 17416 KB Output is correct
12 Correct 125 ms 17424 KB Output is correct
13 Correct 116 ms 17304 KB Output is correct
14 Correct 169 ms 14276 KB Output is correct
15 Correct 176 ms 14432 KB Output is correct
16 Correct 1 ms 720 KB Output is correct
17 Correct 112 ms 14156 KB Output is correct
18 Correct 172 ms 14180 KB Output is correct
19 Correct 159 ms 14276 KB Output is correct
20 Correct 164 ms 14404 KB Output is correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 171 ms 14304 KB Output is correct
24 Correct 107 ms 14284 KB Output is correct
25 Correct 163 ms 14284 KB Output is correct
26 Correct 145 ms 14736 KB Output is correct
27 Correct 137 ms 15436 KB Output is correct
28 Correct 25 ms 5128 KB Output is correct
29 Correct 137 ms 14524 KB Output is correct
30 Correct 114 ms 14028 KB Output is correct
31 Correct 127 ms 12652 KB Output is correct
32 Correct 132 ms 13412 KB Output is correct
33 Correct 222 ms 18344 KB Output is correct
34 Correct 216 ms 20740 KB Output is correct
35 Correct 197 ms 17824 KB Output is correct
36 Correct 166 ms 15948 KB Output is correct
37 Correct 171 ms 16200 KB Output is correct
38 Correct 194 ms 16716 KB Output is correct