QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#718227 | #7855. 不跳棋 | Lu_xZ | 96 | 855ms | 101092kb | C++14 | 2.1kb | 2024-11-06 20:01:11 | 2024-11-06 20:01:11 |
Judging History
answer
#include<bits/stdc++.h>
#define eb emplace_back
#define ep emplace
using namespace std;
using ll = long long;
constexpr int N = 5e5 + 5;
int n, tp, sz[N], tot, rt, fa[N], v[N];
vector<int> g[N];
struct Buc {
vector<ll> a;
int i, j;
void update() {
while(i < a.size() && !a[i]) ++ i;
while(j < a.size() && !a[j]) ++ j;
if(j < a.size() && i == j && a[j] < 2) ++ j;
while(j < a.size() && !a[j]) ++ j;
}
void add(int p, ll v = 1) {
if(p >= a.size()) a.resize(p + 1);
a[p] += v;
}
ll cnt() {
if(j >= a.size()) return 0;
if(i != j) return a[i] * a[j];
return a[i] * (a[i] - 1) / 2;
}
} b[N];
int get_sz(int x, int fa) {
int sz = 1;
for(int y : g[x]) {
if(v[y] || y == fa) continue;
sz += get_sz(y, x);
}
return sz;
}
void get_rt(int x, int fa) {
int mx = 0; sz[x] = 1;
for(int y : g[x]) {
if(v[y] || y == fa) continue;
get_rt(y, x);
mx = max(mx, sz[y]);
sz[x] += sz[y];
}
mx = max(mx, tot - sz[x]);
if(mx <= tot / 2) rt = x;
}
int d[20][N], dep[N];
void dfs1(int x, int fa) {
b[rt].add(d[dep[rt]][x]);
for(int y : g[x]) {
if(v[y] || y == fa) continue;
d[dep[rt]][y] = d[dep[rt]][x] + 1;
dfs1(y, x);
}
}
void dfs(int x) {
v[x] = 1;
dfs1(x, 0);
b[x].update();
if(b[x].j < b[x].a.size()) b[0].add(b[x].i + b[x].j, b[x].cnt());
for(int y : g[x]) {
if(v[y]) continue;
tot = get_sz(y, 0), get_rt(y, 0);
fa[rt] = x;
dep[rt] = dep[x] + 1;
dfs(rt);
}
}
void del(int u) {
int x = u;
while(1) {
if(b[x].j < b[x].a.size()) b[0].add(b[x].i + b[x].j, -b[x].cnt());
b[x].add(d[dep[x]][u], -1);
b[x].update();
if(b[x].j < b[x].a.size()) b[0].add(b[x].i + b[x].j, b[x].cnt());
if(!dep[x]) break;
x = fa[x];
}
b[0].update();
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> tp;
for(int i = 1, u, v; i <= n - 1; ++ i) {
cin >> u >> v;
g[u].eb(v);
g[v].eb(u);
}
tot = n, get_rt(1, 0);
dfs(rt);
for(int i = 1, lst = 0, x; i <= n - 2; ++ i) {
cin >> x;
x = x ^ (lst * tp);
del(x);
cout << b[0].i << ' ' << (lst = b[0].a[b[0].i]) << '\n';
}
return 0;
}
詳細信息
Pretests
Final Tests
Test #1:
score: 4
Accepted
time: 3ms
memory: 36344kb
input:
100 0 1 2 2 3 2 4 3 5 4 6 4 7 3 8 7 9 4 10 3 11 5 12 5 13 11 14 13 15 10 16 5 17 13 18 18 19 3 20 3 21 6 22 18 23 5 24 17 25 6 26 8 27 21 28 8 29 24 30 29 31 2 32 3 33 1 34 31 35 34 36 15 37 2 38 4 39 3 40 37 41 8 42 2 43 28 44 10 45 44 46 35 47 4 48 38 49 9 50 6 51 38 52 30 53 39 54 43 55 43 56 26 ...
output:
1 97 1 94 1 93 1 92 1 91 1 89 1 88 1 85 1 84 1 83 1 82 1 81 1 79 1 77 1 76 1 75 1 73 1 70 1 69 1 68 1 67 1 67 1 67 1 67 1 66 1 65 1 64 1 63 1 62 1 61 1 61 1 60 1 58 1 57 1 57 1 52 1 51 1 50 1 47 1 44 1 41 1 39 1 38 1 37 1 36 1 35 1 34 1 29 1 27 1 26 1 26 1 26 1 25 1 24 1 23 1 22 1 22 1 21 1 20 1 18 ...
result:
ok 98 lines
Test #2:
score: 4
Accepted
time: 0ms
memory: 36376kb
input:
100 0 1 2 1 3 3 4 2 5 2 6 1 7 5 8 6 9 8 10 8 11 3 12 4 13 12 14 4 15 1 16 4 17 14 18 17 19 8 20 17 21 9 22 12 23 12 24 16 25 19 26 21 27 15 28 5 29 12 30 19 31 15 32 22 33 6 34 29 35 2 36 22 37 16 38 19 39 17 40 11 41 13 42 30 43 17 44 24 45 21 46 17 47 40 48 20 49 3 50 13 51 16 52 30 53 43 54 41 55...
output:
1 94 1 91 1 90 1 89 1 84 1 83 1 80 1 78 1 77 1 76 1 73 1 72 1 68 1 66 1 66 1 65 1 65 1 62 1 60 1 58 1 54 1 53 1 52 1 51 1 50 1 49 1 47 1 46 1 45 1 40 1 39 1 36 1 36 1 36 1 35 1 34 1 32 1 28 1 27 1 27 1 27 1 27 1 27 1 27 1 24 1 23 1 23 1 21 1 21 1 20 1 20 1 20 1 20 1 19 1 19 1 19 1 18 1 16 1 15 1 14 ...
result:
ok 98 lines
Test #3:
score: 4
Accepted
time: 4ms
memory: 36408kb
input:
100 0 1 2 1 3 1 4 4 5 3 6 1 7 1 8 3 9 9 10 4 11 10 12 3 13 10 14 9 15 11 16 6 17 15 18 8 19 13 20 18 21 21 22 2 23 19 24 7 25 5 26 23 27 22 28 5 29 15 30 2 31 15 32 31 33 26 34 27 35 18 36 14 37 15 38 11 39 11 40 38 41 2 42 12 43 8 44 11 45 42 46 33 47 11 48 5 49 15 50 6 51 35 52 9 53 18 54 33 55 13...
output:
1 95 1 94 1 92 1 89 1 87 1 84 1 82 1 79 1 74 1 73 1 71 1 68 1 66 1 64 1 62 1 61 1 59 1 58 1 56 1 55 1 54 1 51 1 50 1 50 1 50 1 49 1 49 1 48 1 46 1 45 1 41 1 39 1 38 1 35 1 33 1 32 1 30 1 28 1 28 1 27 1 27 1 25 1 22 1 20 1 20 1 19 1 19 1 19 1 17 1 13 1 13 1 13 1 12 1 12 1 12 1 11 1 11 1 10 1 10 1 10 ...
result:
ok 98 lines
Test #4:
score: 4
Accepted
time: 6ms
memory: 36516kb
input:
1000 0 1 2 1 3 3 4 2 5 4 6 3 7 4 8 2 9 7 10 6 11 2 12 2 13 5 14 11 15 15 16 6 17 16 18 2 19 19 20 14 21 20 22 12 23 23 24 3 25 18 26 9 27 23 28 18 29 12 30 28 31 5 32 9 33 11 34 5 35 21 36 23 37 6 38 30 39 29 40 16 41 22 42 41 43 28 44 39 45 9 46 15 47 22 48 3 49 46 50 24 51 34 52 43 53 4 54 33 55 4...
output:
1 998 1 997 1 996 1 994 1 992 1 990 1 988 1 980 1 979 1 977 1 976 1 974 1 970 1 969 1 966 1 961 1 956 1 955 1 954 1 951 1 950 1 948 1 947 1 944 1 943 1 942 1 940 1 938 1 935 1 934 1 931 1 929 1 928 1 927 1 923 1 922 1 921 1 920 1 919 1 918 1 916 1 915 1 912 1 909 1 904 1 903 1 902 1 901 1 901 1 898 ...
result:
ok 998 lines
Test #5:
score: 4
Accepted
time: 6ms
memory: 36536kb
input:
1000 0 1 2 2 3 1 4 2 5 5 6 4 7 2 8 3 9 8 10 10 11 10 12 6 13 7 14 1 15 1 16 11 17 6 18 2 19 12 20 1 21 20 22 19 23 23 24 15 25 10 26 18 27 27 28 28 29 12 30 26 31 16 32 32 33 24 34 6 35 21 36 9 37 8 38 36 39 26 40 15 41 18 42 41 43 39 44 7 45 23 46 3 47 47 48 28 49 26 50 39 51 4 52 45 53 52 54 6 55 ...
output:
1 997 1 996 1 995 1 994 1 990 1 987 1 985 1 984 1 981 1 980 1 975 1 973 1 971 1 970 1 969 1 968 1 966 1 965 1 964 1 963 1 962 1 961 1 960 1 959 1 957 1 956 1 954 1 953 1 952 1 951 1 945 1 944 1 943 1 941 1 939 1 937 1 933 1 931 1 930 1 928 1 926 1 925 1 924 1 921 1 920 1 920 1 918 1 917 1 916 1 914 ...
result:
ok 998 lines
Test #6:
score: 4
Accepted
time: 0ms
memory: 36492kb
input:
1000 0 1 2 2 3 3 4 2 5 1 6 1 7 1 8 3 9 2 10 10 11 3 12 9 13 9 14 10 15 10 16 16 17 16 18 15 19 6 20 17 21 8 22 3 23 13 24 2 25 20 26 10 27 15 28 19 29 7 30 16 31 22 32 26 33 24 34 6 35 35 36 29 37 8 38 7 39 12 40 19 41 34 42 34 43 34 44 10 45 31 46 40 47 47 48 36 49 29 50 7 51 47 52 33 53 47 54 29 5...
output:
1 997 1 996 1 992 1 986 1 985 1 984 1 983 1 982 1 981 1 979 1 976 1 973 1 971 1 966 1 963 1 962 1 958 1 956 1 953 1 952 1 949 1 948 1 947 1 946 1 944 1 943 1 942 1 941 1 941 1 940 1 939 1 938 1 935 1 933 1 932 1 931 1 930 1 929 1 928 1 925 1 923 1 921 1 920 1 920 1 919 1 916 1 914 1 911 1 908 1 906 ...
result:
ok 998 lines
Test #7:
score: 4
Accepted
time: 249ms
memory: 67000kb
input:
200000 0 1 2 2 3 2 4 1 5 3 6 4 7 4 8 3 9 5 10 8 11 8 12 7 13 11 14 11 15 14 16 15 17 7 18 7 19 15 20 15 21 12 22 14 23 9 24 8 25 18 26 22 27 8 28 2 29 15 30 3 31 24 32 10 33 18 34 12 35 3 36 32 37 20 38 37 39 21 40 1 41 28 42 3 43 21 44 22 45 26 46 44 47 47 48 44 49 27 50 41 51 49 52 6 53 27 54 6 55...
output:
1 199998 1 199997 1 199995 1 199992 1 199990 1 199989 1 199988 1 199985 1 199983 1 199980 1 199979 1 199976 1 199975 1 199973 1 199972 1 199971 1 199968 1 199967 1 199959 1 199957 1 199955 1 199954 1 199953 1 199952 1 199950 1 199948 1 199947 1 199945 1 199944 1 199943 1 199942 1 199941 1 199940 1 1...
result:
ok 199998 lines
Test #8:
score: 4
Accepted
time: 271ms
memory: 60456kb
input:
200000 0 1 2 1 3 1 4 1 5 5 6 4 7 2 8 2 9 9 10 8 11 6 12 10 13 6 14 6 15 6 16 12 17 9 18 15 19 10 20 3 21 8 22 15 23 8 24 6 25 8 26 11 27 14 28 27 29 8 30 9 31 24 32 15 33 19 34 26 35 2 36 17 37 15 38 8 39 30 40 11 41 26 42 17 43 41 44 32 45 9 46 30 47 31 48 41 49 38 50 2 51 42 52 35 53 30 54 10 55 2...
output:
1 199997 1 199996 1 199992 1 199990 1 199988 1 199986 1 199985 1 199981 1 199980 1 199979 1 199978 1 199977 1 199976 1 199974 1 199973 1 199971 1 199970 1 199966 1 199964 1 199963 1 199962 1 199961 1 199960 1 199958 1 199957 1 199956 1 199954 1 199953 1 199949 1 199947 1 199946 1 199945 1 199943 1 1...
result:
ok 199998 lines
Test #9:
score: 4
Accepted
time: 265ms
memory: 60368kb
input:
200000 0 1 2 2 3 2 4 2 5 4 6 3 7 4 8 5 9 6 10 8 11 3 12 8 13 11 14 2 15 11 16 6 17 1 18 6 19 2 20 17 21 19 22 1 23 11 24 2 25 12 26 7 27 3 28 6 29 9 30 17 31 12 32 27 33 21 34 27 35 16 36 22 37 23 38 7 39 11 40 8 41 1 42 6 43 40 44 41 45 44 46 34 47 14 48 20 49 47 50 33 51 21 52 14 53 41 54 52 55 37...
output:
1 199996 1 199995 1 199992 1 199989 1 199988 1 199987 1 199986 1 199984 1 199980 1 199975 1 199974 1 199973 1 199971 1 199970 1 199969 1 199968 1 199963 1 199961 1 199958 1 199955 1 199953 1 199951 1 199950 1 199948 1 199947 1 199945 1 199942 1 199938 1 199936 1 199931 1 199930 1 199928 1 199927 1 1...
result:
ok 199998 lines
Test #10:
score: 4
Accepted
time: 331ms
memory: 97516kb
input:
200000 0 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52...
output:
1 199997 1 199995 1 199993 1 199991 1 199989 1 199987 1 199985 1 199983 1 199981 1 199979 1 199977 1 199975 1 199973 1 199971 1 199969 1 199967 1 199965 1 199963 1 199961 1 199959 1 199957 1 199955 1 199953 1 199951 1 199949 1 199947 1 199945 1 199943 1 199941 1 199939 1 199937 1 199935 1 199933 1 1...
result:
ok 199998 lines
Test #11:
score: 4
Accepted
time: 313ms
memory: 69892kb
input:
200000 0 1 2 1 3 3 4 1 5 1 6 2 7 1 8 7 9 4 10 5 11 7 12 2 13 10 14 11 15 9 16 15 17 13 18 9 19 10 20 14 21 12 22 20 23 22 24 21 25 16 26 20 27 24 28 27 29 27 30 21 31 28 32 24 33 26 34 31 35 29 36 33 37 33 38 38 39 35 40 30 41 36 42 40 43 34 44 44 45 43 46 44 47 45 48 39 49 49 50 41 51 50 52 51 53 4...
output:
1 199997 1 199995 1 199992 1 199988 1 199985 1 199983 1 199981 1 199979 1 199978 1 199976 1 199974 1 199972 1 199971 1 199970 1 199967 1 199964 1 199962 1 199961 1 199959 1 199956 1 199954 1 199951 1 199949 1 199946 1 199943 1 199942 1 199940 1 199939 1 199936 1 199935 1 199934 1 199933 1 199929 1 1...
result:
ok 199998 lines
Test #12:
score: 4
Accepted
time: 314ms
memory: 69740kb
input:
200000 0 1 2 1 3 1 4 4 5 3 6 1 7 2 8 7 9 7 10 9 11 2 12 11 13 12 14 14 15 13 16 10 17 12 18 11 19 14 20 17 21 19 22 12 23 17 24 14 25 19 26 25 27 23 28 26 29 29 30 23 31 31 32 27 33 28 34 26 35 34 36 36 37 34 38 32 39 29 40 40 41 41 42 38 43 37 44 34 45 40 46 38 47 47 48 45 49 40 50 40 51 45 52 50 5...
output:
1 199996 1 199995 1 199992 1 199989 1 199986 1 199985 1 199983 1 199982 1 199981 1 199980 1 199979 1 199976 1 199974 1 199971 1 199969 1 199966 1 199961 1 199960 1 199957 1 199954 1 199953 1 199950 1 199949 1 199946 1 199943 1 199942 1 199938 1 199937 1 199936 1 199935 1 199933 1 199931 1 199929 1 1...
result:
ok 199998 lines
Test #13:
score: 4
Accepted
time: 331ms
memory: 94240kb
input:
200000 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52...
output:
1 199997 1 199995 1 199993 1 199991 1 199989 1 199987 1 199985 1 199983 1 199981 1 199979 1 199977 1 199975 1 199973 1 199971 1 199969 1 199967 1 199965 1 199963 1 199961 1 199959 1 199957 1 199955 1 199953 1 199951 1 199949 1 199947 1 199945 1 199943 1 199941 1 199939 1 199937 1 199935 1 199933 1 1...
result:
ok 199998 lines
Test #14:
score: 4
Accepted
time: 329ms
memory: 95956kb
input:
200000 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52...
output:
1 199997 1 199995 1 199993 1 199991 1 199989 1 199987 1 199985 1 199983 1 199981 1 199979 1 199977 1 199975 1 199973 1 199971 1 199969 1 199967 1 199965 1 199963 1 199961 1 199959 1 199957 1 199955 1 199953 1 199951 1 199949 1 199947 1 199945 1 199943 1 199941 1 199939 1 199937 1 199935 1 199933 1 1...
result:
ok 199998 lines
Test #15:
score: 4
Accepted
time: 231ms
memory: 95880kb
input:
200000 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52...
output:
1 199997 1 199995 1 199993 1 199991 1 199989 1 199987 1 199985 1 199983 1 199981 1 199979 1 199977 1 199975 1 199973 1 199971 1 199969 1 199967 1 199965 1 199963 1 199961 1 199959 1 199957 1 199955 1 199953 1 199951 1 199949 1 199947 1 199945 1 199943 1 199941 1 199939 1 199937 1 199935 1 199933 1 1...
result:
ok 199998 lines
Test #16:
score: 4
Accepted
time: 319ms
memory: 94356kb
input:
200000 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52...
output:
1 199997 1 199995 1 199993 1 199991 1 199989 1 199987 1 199985 1 199983 1 199981 1 199979 1 199977 1 199975 1 199973 1 199971 1 199969 1 199967 1 199965 1 199963 1 199961 1 199959 1 199957 1 199955 1 199953 1 199951 1 199949 1 199947 1 199945 1 199943 1 199941 1 199939 1 199937 1 199935 1 199933 1 1...
result:
ok 199998 lines
Test #17:
score: 4
Accepted
time: 240ms
memory: 67956kb
input:
200000 1 1 2 1 3 2 4 1 5 3 6 1 7 7 8 7 9 4 10 4 11 11 12 12 13 7 14 10 15 1 16 5 17 11 18 11 19 1 20 19 21 18 22 20 23 21 24 21 25 6 26 24 27 2 28 8 29 29 30 6 31 4 32 14 33 2 34 3 35 18 36 23 37 35 38 10 39 28 40 35 41 17 42 1 43 5 44 14 45 23 46 35 47 10 48 10 49 20 50 41 51 14 52 21 53 7 54 5 55 ...
output:
1 199998 1 199997 1 199996 1 199994 1 199991 1 199990 1 199989 1 199988 1 199986 1 199985 1 199984 1 199982 1 199981 1 199978 1 199977 1 199974 1 199973 1 199970 1 199968 1 199963 1 199962 1 199961 1 199958 1 199957 1 199956 1 199955 1 199954 1 199949 1 199948 1 199947 1 199944 1 199942 1 199938 1 1...
result:
ok 199998 lines
Test #18:
score: 4
Accepted
time: 254ms
memory: 70812kb
input:
200000 1 1 2 2 3 2 4 2 5 4 6 3 7 5 8 5 9 9 10 1 11 2 12 1 13 3 14 10 15 4 16 11 17 6 18 8 19 6 20 7 21 15 22 19 23 20 24 12 25 14 26 18 27 22 28 28 29 16 30 30 31 23 32 9 33 7 34 24 35 7 36 9 37 15 38 8 39 18 40 4 41 30 42 22 43 17 44 17 45 9 46 22 47 21 48 44 49 37 50 44 51 23 52 42 53 16 54 43 55 ...
output:
1 199997 1 199992 1 199991 1 199990 1 199989 1 199986 1 199984 1 199982 1 199980 1 199979 1 199976 1 199975 1 199972 1 199971 1 199970 1 199969 1 199966 1 199965 1 199964 1 199962 1 199960 1 199954 1 199953 1 199950 1 199949 1 199948 1 199945 1 199944 1 199943 1 199942 1 199941 1 199940 1 199938 1 1...
result:
ok 199998 lines
Test #19:
score: 4
Accepted
time: 309ms
memory: 68816kb
input:
200000 1 1 2 1 3 2 4 3 5 5 6 5 7 1 8 3 9 8 10 8 11 7 12 11 13 3 14 4 15 7 16 12 17 9 18 10 19 19 20 15 21 16 22 13 23 13 24 14 25 17 26 17 27 19 28 18 29 24 30 21 31 29 32 24 33 30 34 31 35 34 36 27 37 37 38 34 39 33 40 38 41 34 42 42 43 36 44 35 45 43 46 44 47 41 48 43 49 47 50 48 51 42 52 46 53 49...
output:
1 199996 1 199995 1 199993 1 199992 1 199990 1 199987 1 199985 1 199983 1 199982 1 199980 1 199979 1 199978 1 199977 1 199974 1 199973 1 199971 1 199968 1 199964 1 199960 1 199957 1 199955 1 199950 1 199948 1 199947 1 199944 1 199943 1 199941 1 199939 1 199938 1 199935 1 199933 1 199932 1 199931 1 1...
result:
ok 199998 lines
Test #20:
score: 4
Accepted
time: 308ms
memory: 72348kb
input:
200000 1 1 2 1 3 3 4 3 5 2 6 3 7 6 8 8 9 9 10 6 11 10 12 9 13 8 14 10 15 10 16 16 17 15 18 16 19 18 20 17 21 21 22 20 23 22 24 19 25 21 26 22 27 26 28 23 29 24 30 29 31 30 32 31 33 30 34 32 35 35 36 34 37 36 38 38 39 37 40 35 41 36 42 38 43 38 44 41 45 44 46 41 47 47 48 44 49 44 50 49 51 48 52 49 53...
output:
1 199997 1 199996 1 199994 1 199993 1 199992 1 199991 1 199987 1 199985 1 199984 1 199983 1 199981 1 199979 1 199976 1 199973 1 199971 1 199969 1 199968 1 199966 1 199964 1 199960 1 199958 1 199956 1 199955 1 199953 1 199950 1 199947 1 199945 1 199943 1 199942 1 199940 1 199936 1 199934 1 199931 1 1...
result:
ok 199998 lines
Test #21:
score: 0
Runtime Error
input:
500000 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 26 1 27 1 28 1 29 1 30 1 31 1 32 1 33 1 34 1 35 1 36 1 37 1 38 1 39 1 40 1 41 1 42 1 43 1 44 1 45 1 46 1 47 1 48 1 49 1 50 1 51 1 52 1 53 1 54 1 55 1 56 1 57 1 58 1 59 1 60 1 61...
output:
result:
Test #22:
score: 4
Accepted
time: 855ms
memory: 100648kb
input:
500000 1 1 2 1 3 2 4 2 5 3 6 2 7 1 8 5 9 5 10 2 11 11 12 9 13 9 14 13 15 12 16 11 17 11 18 12 19 12 20 3 21 7 22 8 23 5 24 12 25 8 26 10 27 22 28 21 29 14 30 29 31 27 32 2 33 33 34 11 35 23 36 33 37 17 38 22 39 25 40 22 41 26 42 42 43 26 44 8 45 28 46 24 47 1 48 17 49 19 50 15 51 38 52 13 53 18 54 1...
output:
1 499998 1 499997 1 499995 1 499994 1 499993 1 499992 1 499991 1 499990 1 499988 1 499987 1 499986 1 499985 1 499983 1 499981 1 499977 1 499976 1 499974 1 499973 1 499971 1 499970 1 499969 1 499968 1 499965 1 499957 1 499949 1 499948 1 499947 1 499946 1 499941 1 499939 1 499938 1 499934 1 499933 1 4...
result:
ok 499998 lines
Test #23:
score: 4
Accepted
time: 799ms
memory: 100068kb
input:
500000 1 1 2 1 3 3 4 4 5 2 6 6 7 4 8 8 9 1 10 9 11 1 12 3 13 10 14 8 15 4 16 8 17 8 18 9 19 14 20 14 21 20 22 14 23 19 24 9 25 19 26 20 27 11 28 23 29 7 30 29 31 12 32 11 33 13 34 5 35 12 36 22 37 13 38 4 39 19 40 1 41 26 42 14 43 37 44 25 45 34 46 32 47 32 48 43 49 7 50 22 51 16 52 8 53 41 54 34 55...
output:
1 499998 1 499997 1 499996 1 499994 1 499989 1 499987 1 499986 1 499985 1 499979 1 499975 1 499974 1 499972 1 499971 1 499970 1 499967 1 499966 1 499965 1 499964 1 499963 1 499961 1 499959 1 499958 1 499956 1 499952 1 499946 1 499943 1 499942 1 499940 1 499939 1 499938 1 499934 1 499933 1 499932 1 4...
result:
ok 499998 lines
Test #24:
score: 4
Accepted
time: 821ms
memory: 101056kb
input:
500000 1 1 2 1 3 1 4 2 5 4 6 3 7 5 8 3 9 4 10 4 11 7 12 1 13 10 14 10 15 3 16 1 17 5 18 7 19 8 20 8 21 9 22 22 23 17 24 12 25 6 26 17 27 7 28 7 29 10 30 28 31 5 32 4 33 18 34 25 35 32 36 27 37 11 38 11 39 1 40 34 41 34 42 34 43 3 44 31 45 32 46 25 47 10 48 31 49 4 50 39 51 29 52 50 53 12 54 45 55 38...
output:
1 499998 1 499997 1 499995 1 499994 1 499990 1 499987 1 499986 1 499985 1 499984 1 499983 1 499981 1 499980 1 499979 1 499977 1 499976 1 499975 1 499973 1 499972 1 499967 1 499964 1 499962 1 499961 1 499959 1 499957 1 499955 1 499954 1 499953 1 499952 1 499951 1 499949 1 499948 1 499947 1 499944 1 4...
result:
ok 499998 lines
Test #25:
score: 4
Accepted
time: 849ms
memory: 101092kb
input:
500000 1 1 2 1 3 1 4 3 5 1 6 6 7 3 8 4 9 3 10 8 11 10 12 2 13 11 14 10 15 5 16 13 17 8 18 12 19 3 20 3 21 10 22 17 23 5 24 18 25 21 26 10 27 2 28 27 29 21 30 14 31 9 32 2 33 26 34 28 35 24 36 27 37 19 38 2 39 37 40 39 41 35 42 31 43 20 44 21 45 15 46 7 47 5 48 25 49 13 50 32 51 50 52 4 53 7 54 38 55...
output:
1 499992 1 499988 1 499987 1 499986 1 499985 1 499984 1 499982 1 499978 1 499977 1 499976 1 499974 1 499972 1 499971 1 499970 1 499969 1 499967 1 499966 1 499965 1 499960 1 499958 1 499957 1 499955 1 499947 1 499941 1 499940 1 499933 1 499932 1 499931 1 499928 1 499927 1 499926 1 499925 1 499924 1 4...
result:
ok 499998 lines