# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
288504 | rama_pang | City (JOI17_city) | C++14 | 609 ms | 53432 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
void Encode(int N, int A[], int B[]) {
// Euler tour, send information about the left end
// and the interval length. This scores 30 points.
// To improve, notice that representing the interval
// length is wasteful - we can add dummy nodes to
// force interval lengths into a smaller value range.
// If we choose to represent the interval lengths by
// r^0, r^1, r^2, r^3, ..., then the root node's size
// can be multiplied by a factor of r^d, where d is
// the depth of the subtree (d <= 18). Thus for the
// enter time, we have N r^d values, and for the interval
// length, we have log(N r^d, r) values - thus the maximum
// value is N r^d log(N r^d, r) = N r^d (log(N, r) + d).
// Optimizing this function for N = 250000 and d = 18 yields
// r = 1.053 as the optimal ratio, and we need 27.2877 bits.
// Accounting for integer rounding, this is below the needed
// 28 bits for perfect score.
static vector<int> lengths;
auto GenerateLengths = [&]() {
if (!lengths.empty()) {
return;
}
const auto OptimalRatio = [&]() {
const auto Eval = [&](double x) -> double {
const double MAXN = 250000;
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |