Submission #489158

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
489158	2021-11-21T10:31:14 Z	flappybird	City (JOI17_city)	C++14	92 / 100	421 ms	60328 KB

Encoder

#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAX 800
namespace {
	ll opof[MAX]; //onepointofive
	vector<ll> adj[303030];
	ll ord[303030];
	ll num[303030];
	ll tnum[303030];
	ll cnt = 0;
}
ll dfs(ll x, ll p = -1) {
	num[x] = 1;
	ord[x] = ++cnt;
	ll sum = 0;
	for (auto v : adj[x]) {
		if (v == p) continue;
		ll res = dfs(v, x);
		num[x] += res;
		sum += res;
		cnt = ord[x] + sum;
	}
	tnum[x] = lower_bound(opof, opof + MAX, num[x]) - opof;
	num[x] = opof[tnum[x]];
	return num[x];
}
void Encode(int N, int A[], int B[]) {
	ll i;
	for (i = 1; i < MAX; i++) opof[i] = max(opof[i - 1] + 1, opof[i - 1] * 21 / 20);
	for (i = 0; i < N - 1; i++) adj[A[i]].push_back(B[i]), adj[B[i]].push_back(A[i]);
	dfs(0);
	for (i = 0; i < N; i++) {
		Code(i, ord[i] * (MAX) + tnum[i]);
	}
}

Device

#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAX 800

ll opof[MAX];

void InitDevice() {
	ll i;
	for (i = 1; i < MAX; i++) opof[i] = max(opof[i - 1] + 1, opof[i - 1] * 21 / 20);	
}

int Answer(long long S, long long T) {
	ll sl, sr, tl, tr;
	sl = S / MAX;
	tl = T / MAX;
	sr = sl + opof[S % MAX];
	tr = tl + opof[T % MAX];
	if (sl <= tl && tr <= sr) return 1;
	else if (tl <= sl && sr <= tr) return 0;
	else return 2;
}

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	7724 KB	Output is correct
2	Correct	3 ms	7688 KB	Output is correct
3	Correct	4 ms	7684 KB	Output is correct
4	Correct	3 ms	7684 KB	Output is correct
5	Correct	4 ms	7692 KB	Output is correct
6	Correct	4 ms	7684 KB	Output is correct
7	Correct	4 ms	7696 KB	Output is correct
8	Correct	4 ms	7684 KB	Output is correct
9	Correct	4 ms	7692 KB	Output is correct
10	Correct	4 ms	7684 KB	Output is correct
11	Correct	4 ms	7684 KB	Output is correct
12	Correct	4 ms	7692 KB	Output is correct

Subtask #2

84.0 / 92.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	163 ms	16292 KB	Output is correct - L = 597601
2	Correct	152 ms	16168 KB	Output is correct - L = 628001
3	Correct	152 ms	16360 KB	Output is correct - L = 578401
4	Correct	161 ms	16296 KB	Output is correct - L = 580801
5	Correct	385 ms	52084 KB	Output is correct - L = 239564801
6	Correct	419 ms	58968 KB	Output is correct - L = 242566401
7	Correct	404 ms	59004 KB	Output is correct - L = 244675201
8	Correct	398 ms	60328 KB	Output is correct - L = 266032801
9	Partially correct	334 ms	59660 KB	Output is partially correct - L = 398266401
10	Partially correct	316 ms	59580 KB	Output is partially correct - L = 394175201
11	Partially correct	330 ms	59688 KB	Output is partially correct - L = 456160801
12	Partially correct	337 ms	59536 KB	Output is partially correct - L = 413756801
13	Partially correct	361 ms	59304 KB	Output is partially correct - L = 319140001
14	Correct	380 ms	59032 KB	Output is correct - L = 260402401
15	Correct	152 ms	23112 KB	Output is correct - L = 589601
16	Correct	154 ms	23164 KB	Output is correct - L = 598401
17	Correct	161 ms	23212 KB	Output is correct - L = 576001
18	Partially correct	364 ms	58448 KB	Output is partially correct - L = 434440801
19	Correct	376 ms	58564 KB	Output is correct - L = 200000001
20	Correct	370 ms	58236 KB	Output is correct - L = 200000001
21	Partially correct	380 ms	58876 KB	Output is partially correct - L = 413756001
22	Correct	392 ms	58380 KB	Output is correct - L = 201447201
23	Correct	375 ms	58248 KB	Output is correct - L = 201987201
24	Correct	387 ms	58368 KB	Output is correct - L = 205091201
25	Correct	384 ms	57872 KB	Output is correct - L = 205993601
26	Correct	399 ms	57992 KB	Output is correct - L = 208542401
27	Correct	421 ms	58016 KB	Output is correct - L = 209227201