oj.uz

Submission #543126

# Submission time Handle Problem Language Result Execution time Memory
543126 2022-03-29T11:40:51 Z square1001 Road Construction (JOI21_road_construction) C++14
100 / 100
 216 ms 20664 KB 
#include <set>
#include <cmath>
#include <cstdio>
#include <cstdint>
#include <algorithm>
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[3014656], 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 162 ms 12972 KB Output is correct
2 Correct 158 ms 12976 KB Output is correct
3 Correct 25 ms 5196 KB Output is correct
4 Correct 25 ms 5156 KB Output is correct
5 Correct 149 ms 11948 KB Output is correct
6 Correct 71 ms 8372 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 19460 KB Output is correct
2 Correct 135 ms 18212 KB Output is correct
3 Correct 23 ms 5068 KB Output is correct
4 Correct 133 ms 17976 KB Output is correct
5 Correct 117 ms 17376 KB Output is correct
6 Correct 123 ms 17364 KB Output is correct
7 Correct 116 ms 17284 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 14280 KB Output is correct
2 Correct 179 ms 14516 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 111 ms 14272 KB Output is correct
5 Correct 173 ms 14172 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 14280 KB Output is correct
2 Correct 179 ms 14516 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 111 ms 14272 KB Output is correct
5 Correct 173 ms 14172 KB Output is correct
6 Correct 161 ms 14284 KB Output is correct
7 Correct 168 ms 14280 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 169 ms 14308 KB Output is correct
11 Correct 108 ms 14160 KB Output is correct
12 Correct 164 ms 14256 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 12972 KB Output is correct
2 Correct 158 ms 12976 KB Output is correct
3 Correct 25 ms 5196 KB Output is correct
4 Correct 25 ms 5156 KB Output is correct
5 Correct 149 ms 11948 KB Output is correct
6 Correct 71 ms 8372 KB Output is correct
7 Correct 136 ms 14688 KB Output is correct
8 Correct 130 ms 15428 KB Output is correct
9 Correct 25 ms 5196 KB Output is correct
10 Correct 126 ms 14496 KB Output is correct
11 Correct 112 ms 13960 KB Output is correct
12 Correct 127 ms 12664 KB Output is correct
13 Correct 135 ms 13420 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 12972 KB Output is correct
2 Correct 158 ms 12976 KB Output is correct
3 Correct 25 ms 5196 KB Output is correct
4 Correct 25 ms 5156 KB Output is correct
5 Correct 149 ms 11948 KB Output is correct
6 Correct 71 ms 8372 KB Output is correct
7 Correct 137 ms 19460 KB Output is correct
8 Correct 135 ms 18212 KB Output is correct
9 Correct 23 ms 5068 KB Output is correct
10 Correct 133 ms 17976 KB Output is correct
11 Correct 117 ms 17376 KB Output is correct
12 Correct 123 ms 17364 KB Output is correct
13 Correct 116 ms 17284 KB Output is correct
14 Correct 171 ms 14280 KB Output is correct
15 Correct 179 ms 14516 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 111 ms 14272 KB Output is correct
18 Correct 173 ms 14172 KB Output is correct
19 Correct 161 ms 14284 KB Output is correct
20 Correct 168 ms 14280 KB Output is correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 1 ms 596 KB Output is correct
23 Correct 169 ms 14308 KB Output is correct
24 Correct 108 ms 14160 KB Output is correct
25 Correct 164 ms 14256 KB Output is correct
26 Correct 136 ms 14688 KB Output is correct
27 Correct 130 ms 15428 KB Output is correct
28 Correct 25 ms 5196 KB Output is correct
29 Correct 126 ms 14496 KB Output is correct
30 Correct 112 ms 13960 KB Output is correct
31 Correct 127 ms 12664 KB Output is correct
32 Correct 135 ms 13420 KB Output is correct
33 Correct 213 ms 18380 KB Output is correct
34 Correct 216 ms 20664 KB Output is correct
35 Correct 187 ms 17888 KB Output is correct
36 Correct 172 ms 16096 KB Output is correct
37 Correct 174 ms 16384 KB Output is correct
38 Correct 184 ms 16852 KB Output is correct