| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 300540 |
2020-09-17T09:05:42 Z |
mode149256 |
City (JOI17_city) |
C++14 |
|
625 ms |
70872 KB |
/*input
*/
#include <bits/stdc++.h>
#include "Encoder.h"
using namespace std;
namespace my_template {
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;
#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"
const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;
template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }
template<typename T>
void print(vector<T> vec, string name = "") {
cout << name;
for (auto u : vec)
cout << u << ' ';
cout << '\n';
}
}
using namespace my_template;
const int MOD = 1000000007;
const ll INF = std::numeric_limits<ll>::max();
const int MX = 250101;
vi lens1;
int n;
vii edges(MX);
int piv = 0;
vi st(MX);
vi ilgis(MX);
void genLens1() {
double R = 1.05;
int cur = 1;
while (cur < 180 * MX) {
lens1.emplace_back(cur);
cur = max(cur + 1, (int)round(R * cur));
}
}
void dfs(int x, int p) {
st[x] = piv++;
for (auto u : edges[x]) {
if (u != p)
dfs(u, x);
}
int ind = lower_bound(lens1.begin(), lens1.end(), piv - st[x]) - lens1.begin();
piv = st[x] + lens1[ind];
ilgis[x] = ind;
}
void Encode(int N, int A[], int B[])
{
n = N;
genLens1();
for (int i = 0; i < N - 1; ++i)
{
edges[A[i]].emplace_back(B[i]);
edges[B[i]].emplace_back(A[i]);
}
dfs(0, -1);
for (int i = 0; i < N; ++i) {
// printf("i = %d, code = %lld, st = %d, ilgis = %d\n", i, (ll)st[i]*lens1.size() + ilgis[i], st[i], lens1[ilgis[i]]);
Code(i, (ll)st[i]*lens1.size() + ilgis[i]);
}
}
/*input
*/
#include <bits/stdc++.h>
#include "Device.h"
using namespace std;
namespace my_template {
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;
#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"
const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;
template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }
template<typename T>
void print(vector<T> vec, string name = "") {
cout << name;
for (auto u : vec)
cout << u << ' ';
cout << '\n';
}
}
using namespace my_template;
const int MOD = 1000000007;
const ll INF = std::numeric_limits<ll>::max();
const int MX = 250101;
vi lens2;
void genLens2() {
double R = 1.05;
int cur = 1;
while (cur < 180 * MX) {
lens2.emplace_back(cur);
cur = max(cur + 1, (int)round(R * cur));
}
}
void InitDevice()
{
genLens2();
}
int Answer(ll S, ll T)
{
int sx = S / lens2.size();
int sy = T / lens2.size();
int xlen = lens2[S % lens2.size()];
int ylen = lens2[T % lens2.size()];
// printf("S = %d, st = %d, ilgis = %d\n", S, sx, xlen);
// printf("T = %d, st = %d, ilgis = %d\n", S, sy, ylen);
if (sx <= sy and sy + ylen <= sx + xlen) return 1;
else if (sy <= sx and sx + xlen <= sy + ylen) return 0;
else return 2;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
16384 KB |
Output is correct |
| 2 |
Correct |
7 ms |
16384 KB |
Output is correct |
| 3 |
Correct |
6 ms |
16384 KB |
Output is correct |
| 4 |
Correct |
6 ms |
16384 KB |
Output is correct |
| 5 |
Correct |
7 ms |
16384 KB |
Output is correct |
| 6 |
Correct |
6 ms |
16384 KB |
Output is correct |
| 7 |
Correct |
7 ms |
16384 KB |
Output is correct |
| 8 |
Correct |
7 ms |
16384 KB |
Output is correct |
| 9 |
Correct |
6 ms |
16384 KB |
Output is correct |
| 10 |
Correct |
7 ms |
16384 KB |
Output is correct |
| 11 |
Correct |
6 ms |
16384 KB |
Output is correct |
| 12 |
Correct |
6 ms |
16384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
227 ms |
30448 KB |
Output is correct - L = 236800 |
| 2 |
Correct |
233 ms |
30704 KB |
Output is correct - L = 236160 |
| 3 |
Correct |
231 ms |
30456 KB |
Output is correct - L = 237760 |
| 4 |
Correct |
238 ms |
30704 KB |
Output is correct - L = 239680 |
| 5 |
Correct |
596 ms |
69112 KB |
Output is correct - L = 97549440 |
| 6 |
Correct |
600 ms |
69360 KB |
Output is correct - L = 97028800 |
| 7 |
Correct |
625 ms |
69008 KB |
Output is correct - L = 97894720 |
| 8 |
Correct |
599 ms |
68464 KB |
Output is correct - L = 117280320 |
| 9 |
Correct |
511 ms |
70872 KB |
Output is correct - L = 159344640 |
| 10 |
Correct |
504 ms |
70624 KB |
Output is correct - L = 157667520 |
| 11 |
Correct |
506 ms |
70872 KB |
Output is correct - L = 182460800 |
| 12 |
Correct |
497 ms |
70872 KB |
Output is correct - L = 165499200 |
| 13 |
Correct |
552 ms |
69856 KB |
Output is correct - L = 127694400 |
| 14 |
Correct |
587 ms |
69360 KB |
Output is correct - L = 104191680 |
| 15 |
Correct |
227 ms |
30648 KB |
Output is correct - L = 242880 |
| 16 |
Correct |
234 ms |
30448 KB |
Output is correct - L = 247360 |
| 17 |
Correct |
230 ms |
30448 KB |
Output is correct - L = 232960 |
| 18 |
Correct |
556 ms |
69592 KB |
Output is correct - L = 173772800 |
| 19 |
Correct |
575 ms |
69600 KB |
Output is correct - L = 79999680 |
| 20 |
Correct |
614 ms |
69600 KB |
Output is correct - L = 79999680 |
| 21 |
Correct |
586 ms |
69344 KB |
Output is correct - L = 165498880 |
| 22 |
Correct |
573 ms |
69600 KB |
Output is correct - L = 80575360 |
| 23 |
Correct |
573 ms |
69344 KB |
Output is correct - L = 80791360 |
| 24 |
Correct |
581 ms |
69360 KB |
Output is correct - L = 82032960 |
| 25 |
Correct |
578 ms |
69200 KB |
Output is correct - L = 82393920 |
| 26 |
Correct |
610 ms |
69360 KB |
Output is correct - L = 83413440 |
| 27 |
Correct |
613 ms |
69104 KB |
Output is correct - L = 83687360 |
