Submission #489157

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
489157	2021-11-21T10:30:28 Z	flappybird	City (JOI17_city)	C++14	8 / 100	196 ms	16184 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[MAX];
	ll ord[MAX];
	ll num[MAX];
	ll tnum[MAX];
	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	1 ms	640 KB	Output is correct
2	Correct	1 ms	628 KB	Output is correct
3	Correct	0 ms	624 KB	Output is correct
4	Correct	0 ms	640 KB	Output is correct
5	Correct	0 ms	640 KB	Output is correct
6	Correct	0 ms	628 KB	Output is correct
7	Correct	1 ms	636 KB	Output is correct
8	Correct	0 ms	628 KB	Output is correct
9	Correct	0 ms	624 KB	Output is correct
10	Correct	0 ms	640 KB	Output is correct
11	Correct	1 ms	620 KB	Output is correct
12	Correct	0 ms	640 KB	Output is correct

Subtask #2

0 / 92.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	153 ms	16052 KB	Output is correct - L = 597601
2	Correct	154 ms	16132 KB	Output is correct - L = 628001
3	Correct	196 ms	16132 KB	Output is correct - L = 578401
4	Correct	160 ms	16184 KB	Output is correct - L = 580801
5	Runtime error	51 ms	11828 KB	Execution killed with signal 11
6	Halted	0 ms	0 KB	-