#include "Encoder.h"
#include <vector>
using namespace std;
vector<int> edge[250000];
vector<int> range;
int in[250000],p[250000];
int cnt;
void dfs(int x,int from) {
in[x] =cnt++;
for (auto to : edge[x]) {
if (to == from) continue;
dfs(to, x);
}
if (in[x] == cnt - 1) return;
int &e=p[x];
while (in[x] + range[e] < cnt - 1) ++e;
cnt = in[x] + range[e] + 1;
}
void Encode(int N, int A[], int B[])
{
//const double r = 1.055645;
const double r = 1.120438;
range.push_back(0);
for (int i = 1;i<128; ++i) {
int ar = r * range.back();
if (range.back() == ar) ++ar;
range.push_back(ar);
}
for (int i = 0; i < N-1; ++i) {
edge[B[i]].push_back(A[i]);
edge[A[i]].push_back(B[i]);
}
dfs(0,-1);
for (int i = 0; i < N ; ++i)
Code(i, in[i] + (p[i] << 21));
}
#include "Device.h"
#include <vector>
using namespace std;
vector<int> a;
void InitDevice()
{
const double r = 1.120438;
a.push_back(0);
for (int i = 1; i < 128; ++i) {
int ar = a.back()*r;
if (a.back() == ar)++ar;
a.push_back(ar);
}
}
int Answer(long long S, long long T)
{
int ss = S & ((1 << 21) - 1);
int ts= T & ((1 << 21) - 1);
int se = ss+a[S >> 21];
int te = ts+a[T >> 21];
if (ss <= ts && te <= se) return 1;
if (ts <= ss && se <= te) return 0;
return 2;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
12272 KB |
Output is correct |
2 |
Correct |
9 ms |
12272 KB |
Output is correct |
3 |
Correct |
10 ms |
12272 KB |
Output is correct |
4 |
Correct |
9 ms |
12528 KB |
Output is correct |
5 |
Correct |
9 ms |
12272 KB |
Output is correct |
6 |
Correct |
9 ms |
12528 KB |
Output is correct |
7 |
Correct |
9 ms |
12272 KB |
Output is correct |
8 |
Correct |
9 ms |
12272 KB |
Output is correct |
9 |
Correct |
9 ms |
12272 KB |
Output is correct |
10 |
Correct |
10 ms |
12272 KB |
Output is correct |
11 |
Correct |
9 ms |
12528 KB |
Output is correct |
12 |
Correct |
9 ms |
12272 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
211 ms |
20160 KB |
Output is correct - L = 111149056 |
2 |
Correct |
200 ms |
19952 KB |
Output is correct - L = 113246208 |
3 |
Correct |
200 ms |
20136 KB |
Output is correct - L = 113246208 |
4 |
Correct |
200 ms |
19952 KB |
Output is correct - L = 113246208 |
5 |
Correct |
550 ms |
56096 KB |
Output is correct - L = 226492416 |
6 |
Correct |
556 ms |
56248 KB |
Output is correct - L = 228589568 |
7 |
Correct |
540 ms |
56480 KB |
Output is correct - L = 226492416 |
8 |
Correct |
540 ms |
55792 KB |
Output is correct - L = 236978176 |
9 |
Correct |
457 ms |
57304 KB |
Output is correct - L = 251658240 |
10 |
Correct |
457 ms |
57512 KB |
Output is correct - L = 253755392 |
11 |
Correct |
459 ms |
56272 KB |
Output is correct - L = 253755392 |
12 |
Correct |
449 ms |
55704 KB |
Output is correct - L = 253755392 |
13 |
Correct |
491 ms |
56960 KB |
Output is correct - L = 241172480 |
14 |
Correct |
530 ms |
56600 KB |
Output is correct - L = 230686720 |
15 |
Correct |
201 ms |
19944 KB |
Output is correct - L = 113246208 |
16 |
Correct |
208 ms |
19952 KB |
Output is correct - L = 113246208 |
17 |
Correct |
202 ms |
20328 KB |
Output is correct - L = 111149056 |
18 |
Correct |
509 ms |
56552 KB |
Output is correct - L = 251658240 |
19 |
Correct |
518 ms |
56872 KB |
Output is correct - L = 251658240 |
20 |
Correct |
516 ms |
56824 KB |
Output is correct - L = 251658240 |
21 |
Correct |
501 ms |
56544 KB |
Output is correct - L = 249561088 |
22 |
Correct |
520 ms |
56288 KB |
Output is correct - L = 249561088 |
23 |
Correct |
522 ms |
56288 KB |
Output is correct - L = 249561088 |
24 |
Correct |
532 ms |
56336 KB |
Output is correct - L = 247463936 |
25 |
Correct |
536 ms |
56304 KB |
Output is correct - L = 245366784 |
26 |
Correct |
556 ms |
56048 KB |
Output is correct - L = 243269632 |
27 |
Correct |
555 ms |
56096 KB |
Output is correct - L = 241172480 |