#include "Encoder.h"
#include <vector>
#include <cstdio>
#include <set>
#include <algorithm>
#define PB push_back
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair < int , int > pii;
const int N = 5e5 + 500;
int L[N], R[N], cur = 0, n;
vector < int > v[N];
void dfs(int x,int lst){
L[x] = cur++;
for(int y : v[x])
if(y != lst)
dfs(y, x);
R[x] = cur;
}
void Encode(int nn, int u1[], int u2[]){
n = nn;
for(int i = 0;i + 1 < n;i++)
v[u1[i]].PB(u2[i]),
v[u2[i]].PB(u1[i]);
dfs(0, 0);
for(int i = 0;i < n;i++){
//printf("i = %d kod = %lld\n", i, (ll)R[i] * (R[i] - 1) / 2LL + L[i]);
Code(i, (ll)R[i] * (R[i] - 1) / 2LL + L[i]);
}
}
#include "Device.h"
#include <cstdio>
typedef long long ll;
void InitDevice(){
return;
}
inline int get_R(ll X){
ll ret = 0;
for(int i = 18;i >= 0;i--){
ret += (1 << i);
if(ret * (ret - 1) / 2LL > X)
ret -= (1 << i);
}
return ret;
}
int Answer(ll A, ll B){
//printf("A = %lld B = %lld\n", A, B);
int R_A = get_R(A);
int R_B = get_R(B);
int L_A = A - R_A * (R_A - 1) / 2LL;
int L_B = B - R_B * (R_B - 1) / 2LL;
//printf("L_A = %d R_A = %d\n", L_A, R_A);
//printf("L_B = %d R_B = %d\n", L_B, R_B);
if(L_B <= L_A && L_A < R_B)
return 0;
if(L_A <= L_B && L_B < R_A)
return 1;
return 2;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
24320 KB |
Output is correct |
2 |
Correct |
16 ms |
24064 KB |
Output is correct |
3 |
Correct |
16 ms |
24064 KB |
Output is correct |
4 |
Correct |
16 ms |
24320 KB |
Output is correct |
5 |
Correct |
15 ms |
24320 KB |
Output is correct |
6 |
Correct |
15 ms |
24064 KB |
Output is correct |
7 |
Correct |
15 ms |
24320 KB |
Output is correct |
8 |
Correct |
15 ms |
24064 KB |
Output is correct |
9 |
Correct |
17 ms |
24064 KB |
Output is correct |
10 |
Correct |
15 ms |
24064 KB |
Output is correct |
11 |
Correct |
16 ms |
24320 KB |
Output is correct |
12 |
Correct |
17 ms |
24064 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
254 ms |
37616 KB |
Output is correct - L = 245349 |
2 |
Correct |
262 ms |
35824 KB |
Output is correct - L = 244649 |
3 |
Correct |
264 ms |
37360 KB |
Output is correct - L = 245349 |
4 |
Correct |
252 ms |
36848 KB |
Output is correct - L = 245349 |
5 |
Incorrect |
573 ms |
77760 KB |
Wrong Answer [6] |
6 |
Halted |
0 ms |
0 KB |
- |