#include "Encoder.h"
#include <stdlib.h>
static const int N = 250000;
static int len[N + 1], offset[N + 1];
static void InitEncoder() {
len[1] = 1;
for (int n = 2, l = 0; n <= N; n++) {
while (1 << l + 1 <= n)
l++;
len[n] = n * (l + 1);
}
offset[0] = 0;
for (int n = 1; n <= N; n++)
offset[n] = offset[n - 1] + len[N] / n;
}
static int *ej[N], eo[N], sz[N];
static void append(int i, int j) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0)
ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
ej[i][o] = j;
}
static void dfs1(int p, int i) {
sz[i] = 1;
for (int o = eo[i]; o--; ) {
int j = ej[i][o];
if (j != p) {
dfs1(i, j);
sz[i] += sz[j];
}
}
}
static void dfs2(int p, int i, int x) {
Code(i, offset[sz[i]] + x / sz[i]);
int j_ = -1;
for (int o = eo[i]; o--; ) {
int j = ej[i][o];
if (j != p && (j_ == -1 || sz[j_] < sz[j]))
j_ = j;
}
if (j_ != -1)
dfs2(i, j_, x), x += len[sz[j_]];
for (int o = eo[i]; o--; ) {
int j = ej[i][o];
if (j != p && j != j_) {
x = (x + sz[j] - 1) / sz[j] * sz[j];
dfs2(i, j, x), x += len[sz[j]];
}
}
}
void Encode(int n, int *ii, int *jj) {
InitEncoder();
for (int i = 0; i < n; i++)
ej[i] = (int *) malloc(2 * sizeof *ej[i]);
for (int h = 0; h < n - 1; h++)
append(ii[h], jj[h]), append(jj[h], ii[h]);
dfs1(-1, 0);
dfs2(-1, 0, 0);
}
#include "Device.h"
static const int N = 250000;
static int len[N + 1], offset[N + 1];
void InitDevice() {
len[1] = 1;
for (int n = 2, l = 0; n <= N; n++) {
while (1 << l + 1 <= n)
l++;
len[n] = n * (l + 1);
}
offset[0] = 0;
for (int n = 1; n <= N; n++)
offset[n] = offset[n - 1] + len[N] / n;
}
static void Decode(long long x, int *a_, int *b_) {
int lower = 0, upper = N + 1;
while (upper - lower > 1) {
int n = (lower + upper) / 2;
if (x >= offset[n])
lower = n;
else
upper = n;
}
int n = upper;
*a_ = (x - offset[n - 1]) * n, *b_ = *a_ + len[n];
}
int Answer(long long x, long long y) {
int tai, tbi, taj, tbj;
Decode(x, &tai, &tbi), Decode(y, &taj, &tbj);
if (taj <= tai && tbi <= tbj)
return 0;
if (tai <= taj && tbj <= tbi)
return 1;
return 2;
}
Compilation message
Encoder.c:6:12: error: variably modified 'len' at file scope
6 | static int len[N + 1], offset[N + 1];
| ^~~
Encoder.c:6:24: error: variably modified 'offset' at file scope
6 | static int len[N + 1], offset[N + 1];
| ^~~~~~
Encoder.c: In function 'InitEncoder':
Encoder.c:11:17: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
11 | while (1 << l + 1 <= n)
| ~~^~~
Encoder.c: At top level:
Encoder.c:20:13: error: variably modified 'ej' at file scope
20 | static int *ej[N], eo[N], sz[N];
| ^~
Encoder.c:20:20: error: variably modified 'eo' at file scope
20 | static int *ej[N], eo[N], sz[N];
| ^~
Encoder.c:20:27: error: variably modified 'sz' at file scope
20 | static int *ej[N], eo[N], sz[N];
| ^~
Encoder.c: In function 'append':
Encoder.c:24:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
24 | if (o >= 2 && (o & o - 1) == 0)
| ~~^~~
Device.c:5:12: error: variably modified 'len' at file scope
5 | static int len[N + 1], offset[N + 1];
| ^~~
Device.c:5:24: error: variably modified 'offset' at file scope
5 | static int len[N + 1], offset[N + 1];
| ^~~~~~
Device.c: In function 'InitDevice':
Device.c:10:17: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
10 | while (1 << l + 1 <= n)
| ~~^~~