| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 61035 |
2018-07-25T06:20:56 Z |
강태규(#1759) |
City (JOI17_city) |
C++11 |
|
522 ms |
56536 KB |
#include "Encoder.h"
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long llong;
static const int MAXN = 2.5e5;
static const double mul = 1.021;
static vector<int> ls;
static void pushElement() {
int x = ls.back();
int y = x * mul;
if (x == y) ++y;
ls.push_back(y);
}
static void init() {
ls.clear();
ls.push_back(1);
while (ls.back() <= MAXN) pushElement();
for (int i = 0; i < 20; ++i) pushElement();
}
static int n;
static vector<int> edge[MAXN];
static int st[MAXN];
static int sz[MAXN];
static int ord;
static int lowbound(int x) {
return lower_bound(ls.begin(), ls.end(), x) - ls.begin();
}
static void dfs(int x, int p) {
st[x] = ord++;
for (int i : edge[x]) {
if (i == p) continue;
dfs(i, x);
}
int l = lowbound(ord - st[x]);
ord = st[x] + ls[sz[x] = l];
}
void Encode(int N, int A[], int B[]) {
n = N;
for (int i = 0; i < n; ++i) edge[i].clear();
init();
for (int i = 0; i < n - 1; ++i) {
edge[A[i]].push_back(B[i]);
edge[B[i]].push_back(A[i]);
}
ord = 0;
dfs(0, -1);
for (int i = 0; i < n; ++i) {
Code(i, st[i] * ls.size() + sz[i]);
}
}
#include "Device.h"
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long llong;
static const int MAXN = 2.5e5;
static const double mul = 1.021;
static vector<int> ls;
static void pushElement() {
int x = ls.back();
int y = x * mul;
if (x == y) ++y;
ls.push_back(y);
}
static void init() {
ls.clear();
ls.push_back(1);
while (ls.back() <= MAXN) pushElement();
for (int i = 0; i < 20; ++i) pushElement();
}
void InitDevice() {
init();
}
int Answer(llong S, llong T) {
int st1 = S / ls.size();
int st2 = T / ls.size();
int ed1 = st1 + ls[S % ls.size()] - 1;
int ed2 = st2 + ls[T % ls.size()] - 1;
if (st1 <= st2 && ed2 <= ed1) return 1;
if (st2 <= st1 && ed1 <= ed2) return 0;
return 2;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
12288 KB |
Output is correct |
| 2 |
Correct |
8 ms |
12360 KB |
Output is correct |
| 3 |
Correct |
8 ms |
12488 KB |
Output is correct |
| 4 |
Correct |
7 ms |
12288 KB |
Output is correct |
| 5 |
Correct |
8 ms |
12488 KB |
Output is correct |
| 6 |
Correct |
8 ms |
12288 KB |
Output is correct |
| 7 |
Correct |
8 ms |
12488 KB |
Output is correct |
| 8 |
Correct |
7 ms |
12288 KB |
Output is correct |
| 9 |
Correct |
7 ms |
12288 KB |
Output is correct |
| 10 |
Correct |
8 ms |
12288 KB |
Output is correct |
| 11 |
Correct |
8 ms |
12288 KB |
Output is correct |
| 12 |
Correct |
8 ms |
12288 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
173 ms |
19392 KB |
Output is correct - L = 361188 |
| 2 |
Correct |
181 ms |
19432 KB |
Output is correct - L = 362204 |
| 3 |
Correct |
174 ms |
19672 KB |
Output is correct - L = 357124 |
| 4 |
Correct |
176 ms |
19440 KB |
Output is correct - L = 360172 |
| 5 |
Correct |
504 ms |
55200 KB |
Output is correct - L = 135866632 |
| 6 |
Correct |
489 ms |
55272 KB |
Output is correct - L = 136931908 |
| 7 |
Correct |
481 ms |
55080 KB |
Output is correct - L = 135383016 |
| 8 |
Correct |
503 ms |
54896 KB |
Output is correct - L = 140786612 |
| 9 |
Correct |
405 ms |
56472 KB |
Output is correct - L = 167854376 |
| 10 |
Correct |
416 ms |
56528 KB |
Output is correct - L = 168844976 |
| 11 |
Correct |
426 ms |
56528 KB |
Output is correct - L = 179622704 |
| 12 |
Correct |
408 ms |
56536 KB |
Output is correct - L = 172313092 |
| 13 |
Correct |
466 ms |
56056 KB |
Output is correct - L = 151992584 |
| 14 |
Correct |
522 ms |
55856 KB |
Output is correct - L = 141529816 |
| 15 |
Correct |
176 ms |
19440 KB |
Output is correct - L = 358140 |
| 16 |
Correct |
177 ms |
19384 KB |
Output is correct - L = 364744 |
| 17 |
Correct |
179 ms |
19448 KB |
Output is correct - L = 357632 |
| 18 |
Correct |
501 ms |
55696 KB |
Output is correct - L = 175929544 |
| 19 |
Correct |
494 ms |
55520 KB |
Output is correct - L = 126999492 |
| 20 |
Correct |
470 ms |
55576 KB |
Output is correct - L = 126999492 |
| 21 |
Correct |
487 ms |
55624 KB |
Output is correct - L = 165297612 |
| 22 |
Correct |
496 ms |
55568 KB |
Output is correct - L = 127029464 |
| 23 |
Correct |
504 ms |
55496 KB |
Output is correct - L = 127372364 |
| 24 |
Correct |
493 ms |
55344 KB |
Output is correct - L = 128328420 |
| 25 |
Correct |
501 ms |
55360 KB |
Output is correct - L = 128525524 |
| 26 |
Correct |
507 ms |
55400 KB |
Output is correct - L = 128592580 |
| 27 |
Correct |
518 ms |
55088 KB |
Output is correct - L = 129267204 |
