#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 250010;
typedef long long ll;
typedef pair<int,int> ii;
static vector<int> grafo[MAXN],sequencia;
static int ini[MAXN],idx[MAXN],dfsCount;
static void build_sequence(){
const long double factor = 1.055645;
sequencia.push_back(0);
sequencia.push_back(1);
for(int i = 2;i<256;i++){
int x = int( factor*sequencia.back() );
if(x == sequencia.back()) x += 1;
sequencia.push_back(x);
}
}
static void dfs(int v,int p){
ini[v] = ++dfsCount;
for(int u : grafo[v]){
if(u == p) continue;
dfs(u,v);
}
int lo = 0, hi = 255, mid, ans = -1;
while(lo <= hi){
mid = (lo + hi)/2;
if(ini[v] + sequencia[mid] >= dfsCount){
ans = mid;
hi = mid - 1;
}
else{
lo = mid + 1;
}
}
idx[v] = ans;
dfsCount = ini[v] + sequencia[ans];
}
static long long coding(int A,int B){
long long davez = A;
davez += (1LL << 20)*ll(B);
return davez;
}
void Encode(int N, int A[], int B[]){
build_sequence();
for(int i = 0;i<N-1;i++){
grafo[A[i]].push_back(B[i]);
grafo[B[i]].push_back(A[i]);
}
dfs(0,-1);
for(int i = 0;i<N;i++){
ini[i]--;
}
for (int i = 0; i < N; ++i) {
Code(i, coding(ini[i],idx[i]) );
}
}
#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
static vector<int> sequencia;
static void build_sequence(){
const long double factor = 1.055645;
sequencia.push_back(0);
sequencia.push_back(1);
for(int i = 2;i<256;i++){
int x = int( factor*sequencia.back() );
if(x == sequencia.back()) x += 1;
sequencia.push_back(x);
}
}
void InitDevice(){
build_sequence();
}
static void Magic(long long X, int &ini, int& fim ){
ini = 0;
fim = 0;
long long temp = (X >> 20);
fim = sequencia[temp];
X -= (temp)*(1 << 20);
ini += X;
fim += ini;
}
int Answer(long long S, long long T){
if(S == T) return 2;
int inia,fima,inib,fimb;
Magic(S,inia,fima);
Magic(T,inib,fimb);
if(inia <= inib && inib <= fima) return 1;
if(inib <= inia && inia <= fimb) return 0;
return 2;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
12544 KB |
Output is correct |
2 |
Correct |
8 ms |
12544 KB |
Output is correct |
3 |
Correct |
9 ms |
12544 KB |
Output is correct |
4 |
Correct |
9 ms |
12544 KB |
Output is correct |
5 |
Correct |
8 ms |
12288 KB |
Output is correct |
6 |
Correct |
8 ms |
12288 KB |
Output is correct |
7 |
Correct |
9 ms |
12544 KB |
Output is correct |
8 |
Correct |
8 ms |
12536 KB |
Output is correct |
9 |
Correct |
8 ms |
12544 KB |
Output is correct |
10 |
Correct |
8 ms |
12544 KB |
Output is correct |
11 |
Correct |
9 ms |
12544 KB |
Output is correct |
12 |
Correct |
10 ms |
12544 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
169 ms |
19464 KB |
Output is correct - L = 101711872 |
2 |
Correct |
170 ms |
19584 KB |
Output is correct - L = 101711872 |
3 |
Correct |
166 ms |
19448 KB |
Output is correct - L = 100663296 |
4 |
Correct |
167 ms |
19384 KB |
Output is correct - L = 101711872 |
5 |
Correct |
524 ms |
55256 KB |
Output is correct - L = 218103808 |
6 |
Correct |
492 ms |
55128 KB |
Output is correct - L = 218103808 |
7 |
Correct |
511 ms |
55280 KB |
Output is correct - L = 219152384 |
8 |
Correct |
503 ms |
54568 KB |
Output is correct - L = 218103808 |
9 |
Correct |
425 ms |
56448 KB |
Output is correct - L = 229638144 |
10 |
Correct |
422 ms |
56576 KB |
Output is correct - L = 231735296 |
11 |
Correct |
413 ms |
56608 KB |
Output is correct - L = 231735296 |
12 |
Correct |
441 ms |
56760 KB |
Output is correct - L = 231735296 |
13 |
Correct |
454 ms |
56040 KB |
Output is correct - L = 223346688 |
14 |
Correct |
473 ms |
55792 KB |
Output is correct - L = 220200960 |
15 |
Correct |
169 ms |
19440 KB |
Output is correct - L = 101711872 |
16 |
Correct |
171 ms |
19432 KB |
Output is correct - L = 101711872 |
17 |
Correct |
169 ms |
19440 KB |
Output is correct - L = 100663296 |
18 |
Correct |
494 ms |
55760 KB |
Output is correct - L = 230686720 |
19 |
Correct |
484 ms |
55600 KB |
Output is correct - L = 230686720 |
20 |
Correct |
489 ms |
55648 KB |
Output is correct - L = 230686720 |
21 |
Correct |
476 ms |
55920 KB |
Output is correct - L = 230686720 |
22 |
Correct |
523 ms |
55616 KB |
Output is correct - L = 230686720 |
23 |
Correct |
517 ms |
55824 KB |
Output is correct - L = 230686720 |
24 |
Correct |
549 ms |
55448 KB |
Output is correct - L = 229638144 |
25 |
Correct |
554 ms |
55440 KB |
Output is correct - L = 228589568 |
26 |
Correct |
537 ms |
55208 KB |
Output is correct - L = 227540992 |
27 |
Correct |
541 ms |
55024 KB |
Output is correct - L = 226492416 |