QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#449289 | #8359. travel | definieren | 15 | 42ms | 125952kb | C++14 | 7.6kb | 2024-06-20 21:33:03 | 2024-06-20 21:33:05 |
Judging History
answer
#include <bits/stdc++.h>
#define fir first
#define sec second
#ifdef LOCAL
#define dbg(x) cerr << "In Line " << __LINE__ << " the " << #x << " = " << x << '\n';
#define dpi(x, y) cerr << "In Line " << __LINE__ << " the " << #x << " = " << x << " ; " << "the " << #y << " = " << y << '\n';
#define dbgf(fmt, args...) fprintf(stderr, fmt, ##args);
#else
#define dbg(x) void();
#define dpi(x, y) void();
#define dbgf(fmt, args...) void();
#endif
using namespace std;
using ll = long long;
using ull = unsigned long long;
using i128 = __int128_t;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using vi = vector<int>;
using vpii = vector<pii>;
bool Mbe;
constexpr int MOD = 998244353;
template<typename T> T add(T a, T b, T p = MOD) { return (a + b >= p) ? (a + b - p) : (a + b); }
template<typename T> T del(T a, T b, T p = MOD) { return (a - b < 0) ? (a - b + p) : (a - b); }
template<typename T> T mul(T a, T b, T p = MOD) { return 1ll * a * b % p; }
template<typename T> T cadd(T &a, T b, T p = MOD) { return a = add(a, b, p); }
template<typename T> T cdel(T &a, T b, T p = MOD) { return a = del(a, b, p); }
template<typename T> T cmul(T &a, T b, T p = MOD) { return a = mul(a, b, p); }
template<typename T> bool cmax(T &a, T b) { return a < b ? a = b, true : false; }
template<typename T> bool cmin(T &a, T b) { return a > b ? a = b, true : false; }
namespace FastIO {
constexpr int LEN = 1 << 20;
char in[LEN + 1], out[LEN + 1];
char *pin = in, *pout = out, *ein = in, *eout = out + LEN;
char gc() { return pin == ein && (ein = (pin = in) + fread(in, 1, LEN, stdin), ein == in) ? EOF : *pin ++; }
void pc(char c) { pout == eout && (fwrite(out, 1, LEN, stdout), pout = out); (*pout ++) = c; return; }
void Flush() { fwrite(out, 1, pout - out, stdout); pout = out; }
template<typename T> T Read() {
T x = 0; int f = 1; char ch = gc();
while (ch < '0' || ch > '9') f = (ch == '-' ? (~f + 1) : f), ch = gc();
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc();
return x * f;
}
template<typename T> void Write(T x, char c) {
static char stk[40]; int tp = 0;
if (x < 0) pc('-'), x = ~x + 1;
do stk[tp++] = x % 10 + 48, x /= 10; while (x);
while (tp --) pc(stk[tp]); pc(c); return;
}
void Read(char *s) {
char ch = gc();
while (!((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') ||
(ch >= '0' && ch <= '9'))) ch = gc();
while ((ch != EOF) && ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') ||
(ch >= '0' && ch <= '9'))) *s = ch, s ++, ch = gc();
*s = '\0'; return;
}
void Write(char *s) {
while (*s != '\0') pc(*s), s ++; return;
}
void Puts(char *s) {
Write(s), pc('\n'); return;
}
}
#define getchar FastIO::gc
#define putchar FastIO::pc
#define Flush FastIO::Flush
#define Read FastIO::Read
#define Write FastIO::Write
#define Puts FastIO::Puts
constexpr int N = 5e5 + 5, LG = 19;
int n, k, op;
namespace Solve2 {
int rt, sz[N], mxp[N], dfn[N], ord[N], dfc, dep[N], bel[N];
pair<int, int> st[LG][N];
priority_queue<pair<int, int> > Q;
vector<int> son, ans, G[N];
vector<pair<int, int>> dis[N], rng[N];
bool mrk[N];
void Get_Root(int u, int fa) {
sz[u] = 1, mxp[u] = 0;
for (auto v : G[u]) if (v ^ fa)
Get_Root(v, u), sz[u] += sz[v], cmax(mxp[u], sz[v]);
cmax(mxp[u], n - sz[u]), rt = mxp[u] < mxp[rt] ? u : rt;
return;
}
void Dfs1(int u, int fa, int anc) {
sz[ord[dfn[u] = ++ dfc] = u] = 1, bel[u] = anc;
st[0][dfn[u]] = make_pair(dep[u] = dep[fa] + 1, fa);
for (auto v : G[u]) if (v ^ fa) Dfs1(v, u, anc), sz[u] += sz[v];
return;
}
pair<int, int> ST_Query(int l, int r) {
int k = __lg(r - l + 1);
return min(st[k][l], st[k][r - (1 << k) + 1]);
}
int Get_Lca(int u, int v) {
if (u == v) return u;
if ((u = dfn[u]) > (v = dfn[v])) swap(u, v);
return ST_Query(u + 1, v).sec;
}
void Main() {
for (int i = 1; i < n; i ++) {
int u = Read<int>(), v = Read<int>();
G[u].emplace_back(v), G[v].emplace_back(u);
}
mxp[0] = n + 1, Get_Root(1, rt = 0);
sz[rt] = dep[rt] = 0, dfn[rt] = dfc = 1, bel[rt] = rt, ord[1] = rt;
for (auto u : G[rt]) son.emplace_back(u), Dfs1(u, rt, u), sz[rt] += sz[u];
for (int i = 1; i < LG; i ++)
for (int j = 1; j + (1 << i) - 1 <= n; j ++)
st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
{
int L = 2 * (n - 1), R = 0;
for (int u = 1; u <= n; u ++) R += dep[u]; R <<= 1;
if ((k & 1) || k < L || k > R) { Puts("-1"); return; }
k = (R - k) >> 1;
};
for (int i = 1; i <= n; i ++) {
if (bel[ord[i]] != bel[ord[i + 1]]) continue;
dis[bel[ord[i]]].emplace_back(dep[Get_Lca(ord[i], ord[i + 1])], ord[i]);
}
for (auto u : son) if (dis[u].size())
sort(dis[u].begin(), dis[u].end()), Q.emplace(make_pair(dis[u].size(), u));
// for (auto u : son) {
// cout << u << ": ";
// for (auto dist : dis[u]) cout << dist.fir << ' ';
// cout << endl;
// }
if (k) {
while (Q.size()) {
int u = Q.top().sec; Q.pop();
int dist, v; tie(dist, v) = dis[u].back();
if (dist < k) k -= dist, dis[u].pop_back(), mrk[v] = true;
else {
while (dis[u].back().fir > k) dis[u].pop_back();
mrk[dis[u].back().sec] = true, k = 0; break;
}
if (dis[u].size()) Q.emplace(dis[u].size(), u);
}
}
for (int l = 1, r; l <= n; l = r + 1) {
r = l;
while (bel[ord[r + 1]] == bel[ord[l]] && mrk[ord[r]]) r ++;
rng[bel[ord[l]]].emplace_back(l, r);
}
{
son.emplace_back(rt);
sort(son.begin(), son.end(), [&](int x, int y) { return rng[x].size() > rng[y].size(); });
// for (auto u : son) for (auto _ : rng[u]) cout << u << ": " << '[' << _.fir << ',' << _.sec << ']' << endl;
// cout << endl;
assert(son.size() >= 2);
int p1 = 0, p2 = 1;
while (p1 < son.size() && p2 < son.size()) {
int u = son[p1], v = son[p2];
while (rng[u].size() && rng[v].size()) {
int l1, r1, l2, r2;
tie(l1, r1) = rng[u].back(), rng[u].pop_back();
tie(l2, r2) = rng[v].back(), rng[v].pop_back();
for (int i = l1; i <= r1; i ++) ans.emplace_back(ord[i]);
for (int i = l2; i <= r2; i ++) ans.emplace_back(ord[i]);
}
if (rng[u].empty()) cmax(p1, p2), p1 ++;
if (rng[v].empty()) cmax(p2, p1), p2 ++;
}
p1 = min(p1, p2);
if (p1 < son.size() && rng[son[p1]].size()) {
assert(rng[son[p1]].size() == 1);
int l, r; tie(l, r) = rng[son[p1]][0];
for (int i = l; i <= r; i ++) Write(ord[i], ' ');
}
for (auto u : ans) Write(u, ' '); Puts("");
};
return;
}
void Clear() {
rt = dfc = 0; while (Q.size()) Q.pop();
son.clear(), ans.clear();
for (int i = 1; i <= n; i ++) {
G[i].clear(), sz[i] = mxp[i] = dfn[i] = ord[i] = dep[i] = 0;
bel[i] = 0, mrk[i] = false, dis[i].clear(), rng[i].clear();
for (int j = 0; j < LG; j ++) st[j][i] = {0, 0};
}
return;
}
}
namespace Solve1 {
vector<int> G[N];
void Main() {
for (int i = 1; i < n; i ++) {
int u = Read<int>(), v = Read<int>();
// G[u].emplace_back(v), G[v].emplace_back(u);
}
Puts("-1");
return;
}
void Clear() {
return;
}
}
void slv() {
n = Read<int>(), k = Read<int>(), op = Read<int>();
if (n == 1) { k ? Puts("-1") : Puts("1"); return; }
if (n == 2) { k == op ? Puts("1 2") : Puts("-1"); return; }
return op == 1 ? (Solve1::Main(), Solve1::Clear()) : (Solve2::Main(), Solve2::Clear());
}
void clr() {
return;
}
bool Med;
int main() {
#ifdef LOCAL
freopen("!in.in", "r", stdin);
freopen("!out.out", "w", stdout);
fprintf(stderr, "%.3lf Mb\n", fabs((&Mbe - &Med) / 1048576.0));
#endif
// int T = 1;
int T = Read<int>();
while (T --) slv(), clr();
Flush();
#ifdef LOCAL
fprintf(stderr, "%d ms\n", (int)clock());
#endif
return 0;
}
詳細信息
Subtask #1:
score: 2
Accepted
Test #1:
score: 2
Accepted
time: 4ms
memory: 51092kb
input:
0
output:
result:
ok Accepted.
Subtask #2:
score: 2
Acceptable Answer
Test #2:
score: 2
Acceptable Answer
time: 8ms
memory: 100300kb
input:
5 9 28 2 8 6 6 3 3 2 9 5 4 1 1 5 5 2 2 7 9 16 2 1 3 7 8 4 2 2 9 9 8 8 6 6 3 3 5 9 12 1 7 5 5 9 9 2 2 8 6 1 1 8 8 4 4 3 9 22 1 8 5 2 4 4 1 1 6 6 9 7 9 9 5 5 3 9 27 1 2 6 4 8 8 1 5 9 9 1 1 7 7 6 6 3
output:
8 4 6 9 1 3 5 7 2 7 9 2 4 6 3 1 5 8 -1 -1 -1
result:
points 0.50 Partially Correct | type = 2
Test #3:
score: 2
Acceptable Answer
time: 11ms
memory: 103356kb
input:
5 9 16 2 4 3 3 1 7 6 2 8 8 6 6 1 1 5 9 5 9 12 1 6 7 5 4 4 1 1 3 3 2 2 7 8 7 7 9 9 14 1 1 2 2 3 6 4 8 9 9 3 3 4 5 4 4 7 9 12 1 9 4 4 1 1 5 3 2 2 6 6 5 8 5 5 7 9 9 1 8 7 7 3 3 2 2 9 4 9 9 1 1 6 6 5
output:
3 4 6 7 8 2 5 9 1 -1 -1 -1 -1
result:
points 0.50 Partially Correct | type = 2
Test #4:
score: 2
Acceptable Answer
time: 3ms
memory: 100600kb
input:
5 9 13 1 4 7 7 8 8 5 1 9 2 5 3 5 5 9 9 6 9 16 2 7 3 1 5 5 8 8 9 2 3 4 9 9 3 3 6 9 26 1 1 3 3 8 8 9 7 4 2 6 6 9 9 4 4 5 9 25 1 5 3 7 2 2 4 4 9 6 1 1 9 9 3 3 8 9 14 1 3 8 8 5 5 4 7 6 6 4 4 2 2 9 9 1
output:
-1 8 5 1 4 3 7 2 6 9 -1 -1 -1
result:
points 0.50 Partially Correct | type = 2
Test #5:
score: 2
Acceptable Answer
time: 11ms
memory: 103472kb
input:
5 9 27 1 8 2 6 9 9 1 4 5 5 1 1 2 2 7 7 3 9 16 2 2 6 6 9 7 8 8 4 1 4 5 4 4 9 9 3 9 30 1 6 7 9 4 4 2 2 5 1 5 5 3 3 7 7 8 9 12 1 4 1 8 6 6 3 2 5 5 1 1 3 3 7 7 9 9 22 1 2 3 7 8 8 1 1 9 9 5 5 3 3 4 6 4
output:
-1 4 8 7 1 5 9 6 2 3 -1 -1 -1
result:
points 0.50 Partially Correct | type = 2
Test #6:
score: 2
Acceptable Answer
time: 7ms
memory: 103156kb
input:
5 9 18 2 7 3 3 8 8 4 4 9 9 1 1 5 2 6 5 6 9 26 2 8 3 3 9 9 5 4 2 2 5 6 7 7 5 5 1 9 25 1 1 5 5 9 9 6 2 4 7 6 6 8 8 4 4 3 9 26 2 1 9 9 4 4 6 5 7 3 7 7 6 6 2 2 8 9 26 2 1 4 4 6 6 8 3 9 9 2 5 8 8 7 7 2
output:
5 6 2 4 8 3 7 1 9 5 8 4 3 2 9 6 1 7 -1 1 3 9 7 5 4 8 6 2 8 1 9 3 4 7 2 6 5
result:
points 0.50 Partially Correct | type = 2
Test #7:
score: 2
Acceptable Answer
time: 7ms
memory: 102924kb
input:
5 9 13 1 2 4 5 8 8 1 6 9 9 7 7 1 1 4 4 3 9 29 2 3 2 1 8 8 4 4 6 6 7 5 2 2 9 9 7 9 15 2 1 3 3 7 7 2 2 9 4 5 5 9 9 6 6 8 9 31 1 2 9 9 8 8 6 6 5 5 4 7 4 4 1 1 3 9 21 2 7 2 2 5 1 4 3 6 6 5 9 4 4 5 5 8
output:
-1 -1 -1 -1 -1
result:
points 0.50 Partially Correct | type = 2
Test #8:
score: 4
Accepted
time: 10ms
memory: 55068kb
input:
5 1 0 1 1 0 2 1 0 2 1 0 1 1 0 2
output:
1 1 1 1 1
result:
ok Accepted.
Subtask #3:
score: 4
Acceptable Answer
Dependency #2:
50%
Acceptable Answer
Test #9:
score: 4
Acceptable Answer
time: 3ms
memory: 103952kb
input:
5 13 37 1 3 12 12 7 4 13 13 11 11 8 8 6 1 2 10 9 9 7 7 5 5 6 6 2 13 42 1 2 4 4 13 13 5 5 7 7 12 8 6 6 9 1 10 10 11 3 9 9 12 12 11 13 15 1 9 2 2 11 12 4 4 5 5 6 6 3 3 11 8 13 13 1 7 11 11 10 10 1 13 48 1 11 3 3 4 12 1 7 5 5 8 8 2 2 1 10 1 1 4 4 6 13 9 9 6 13 68 2 13 4 6 5 2 1 1 9 9 11 11 12 12 7 7 5 ...
output:
-1 -1 -1 -1 2 10 1 3 9 13 11 4 7 12 8 6 5
result:
points 0.50 Partially Correct | type = 2
Test #10:
score: 4
Acceptable Answer
time: 11ms
memory: 102932kb
input:
5 13 34 2 2 7 5 11 13 1 1 3 8 9 9 6 6 11 11 3 3 7 7 12 12 4 4 10 13 17 1 2 7 7 11 11 9 10 12 12 4 6 13 13 4 4 8 8 3 3 1 1 9 9 5 13 33 1 7 6 6 1 1 10 10 13 9 4 11 12 12 13 8 13 2 4 4 13 13 3 5 3 13 17 1 8 11 11 13 13 3 3 5 10 2 2 1 1 6 12 7 6 5 5 4 4 9 9 7 13 15 1 5 1 8 3 2 13 13 11 11 6 6 7 7 9 9 1 ...
output:
1 6 9 8 12 4 10 5 2 11 7 13 3 -1 -1 -1 -1
result:
points 0.50 Partially Correct | type = 2
Test #11:
score: 8
Accepted
time: 0ms
memory: 103804kb
input:
5 13 24 2 1 5 11 12 12 2 2 10 4 9 9 3 6 13 13 8 8 5 5 10 10 3 3 7 13 28 2 13 5 5 7 7 3 9 6 4 10 8 12 1 12 12 6 6 3 3 2 2 10 10 11 13 50 2 4 13 13 8 8 10 10 1 3 5 12 7 7 1 1 9 9 5 5 2 6 2 11 2 13 64 2 10 3 3 9 9 7 7 11 11 5 5 13 6 2 2 8 4 8 1 13 13 8 8 12 13 52 2 13 12 12 8 8 10 5 6 6 11 9 2 7 2 1 10...
output:
2 12 11 5 1 8 13 6 3 9 4 7 10 9 12 8 1 10 4 11 6 2 7 5 13 3 7 4 6 11 13 2 8 5 3 10 9 12 1 13 10 12 3 4 9 6 7 2 11 8 5 1 3 13 1 5 12 6 8 11 10 4 9 7 2
result:
ok Accepted.
Test #12:
score: 4
Acceptable Answer
time: 7ms
memory: 103376kb
input:
5 13 34 1 8 11 11 2 2 10 9 6 3 1 4 13 13 7 7 6 6 12 12 1 1 10 10 5 13 31 1 11 1 1 9 9 5 6 7 7 2 13 4 4 2 2 10 10 12 12 8 8 5 5 3 13 28 2 2 8 8 9 9 6 6 7 4 13 13 11 11 7 7 5 5 1 12 1 1 3 3 10 13 49 1 11 4 4 1 1 8 8 12 12 3 3 7 6 2 13 7 7 5 2 10 10 9 9 5 13 62 1 12 9 9 5 5 6 6 1 1 4 4 2 2 3 8 11 7 10 ...
output:
-1 -1 9 8 2 1 12 3 10 6 5 11 13 4 7 -1 -1
result:
points 0.50 Partially Correct | type = 2
Test #13:
score: 4
Acceptable Answer
time: 7ms
memory: 103908kb
input:
5 13 59 1 10 9 3 8 8 7 7 6 6 12 4 1 13 5 5 12 12 2 2 9 9 1 1 11 13 30 2 9 5 2 1 1 3 3 12 12 8 8 7 7 6 11 10 10 5 5 6 4 6 13 6 13 54 1 11 13 13 12 12 10 9 3 3 5 4 2 6 10 10 7 7 5 5 2 1 2 2 8 13 24 2 2 11 5 12 12 4 8 3 3 6 6 7 7 1 10 9 9 4 4 1 1 11 11 13 13 56 2 3 2 2 8 4 9 9 1 1 5 7 10 10 5 5 11 11 8...
output:
-1 10 11 8 12 3 1 2 9 7 5 4 13 6 -1 7 6 3 8 4 12 5 9 10 11 2 13 1 7 13 10 12 4 6 9 3 1 8 2 5 11
result:
points 0.50 Partially Correct | type = 2
Test #14:
score: 4
Acceptable Answer
time: 4ms
memory: 100268kb
input:
5 13 21 2 1 11 11 10 12 6 6 8 8 2 2 4 4 7 9 5 5 3 13 10 10 3 3 7 13 34 1 11 4 4 12 2 13 13 8 8 5 10 6 7 1 3 6 6 12 12 9 1 5 5 9 13 137 2 7 9 13 12 12 4 4 5 5 10 10 11 11 9 9 8 2 1 8 3 3 1 6 1 13 13 1 13 12 12 2 2 8 8 9 9 3 3 10 1 10 10 6 7 5 5 6 6 11 11 4 13 25 2 6 9 4 12 12 5 5 1 1 3 7 13 13 9 9 8 ...
output:
-1 -1 -1 -1 -1
result:
points 0.50 Partially Correct | type = 2
Test #15:
score: 8
Accepted
time: 9ms
memory: 54408kb
input:
5 1 0 1 1 0 2 1 0 2 1 0 1 1 0 2
output:
1 1 1 1 1
result:
ok Accepted.
Subtask #4:
score: 7
Acceptable Answer
Test #16:
score: 7
Acceptable Answer
time: 8ms
memory: 100584kb
input:
200 9 38 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 26 2 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 10 30 2 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 9 30 2 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 10 28 2 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 41 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 44 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10...
output:
-1 2 1 8 9 3 6 7 4 5 6 3 2 1 9 10 4 8 5 7 5 1 8 9 3 2 7 4 6 3 2 1 9 10 4 7 8 5 6 -1 -1 4 3 2 1 7 8 9 10 5 6 -1 -1 -1 -1 6 2 1 10 3 9 4 8 5 7 1 9 2 7 8 3 6 4 5 2 1 10 3 9 4 7 8 5 6 5 2 1 7 8 9 4 3 6 -1 2 1 8 9 3 6 7 4 5 6 1 10 3 2 9 4 8 5 7 -1 -1 -1 2 1 9 10 3 8 4 7 5 6 -1 6 5 4 3 2 1 7 8...
result:
points 0.50 Partially Correct | type = 2
Test #17:
score: 7
Acceptable Answer
time: 3ms
memory: 103624kb
input:
200 9 8 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 17 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 8 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 10 45 2 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 9 29 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 10 51 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 9 39 2 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 16 2 1 2 2 ...
output:
-1 -1 -1 -1 -1 -1 -1 5 4 3 2 1 6 7 8 9 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 6 5 4 3 2 1 7 8 9 10 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 5 4 3 2 1 6 7 8 9 -1 -1 -1 -1 -1 -1 -1 -1 -1 5 4 3 2 1...
result:
points 0.50 Partially Correct | type = 2
Test #18:
score: 14
Accepted
time: 3ms
memory: 53396kb
input:
2000 1 0 2 1 0 1 1 0 1 1 0 2 1 0 2 1 0 1 1 0 2 1 0 1 1 0 1 1 0 2 1 0 1 1 0 1 1 0 1 1 0 2 1 0 2 1 0 1 1 0 2 1 0 2 1 0 1 1 0 1 1 0 2 1 0 1 1 0 2 1 0 2 1 0 1 1 0 2 1 0 2 1 0 1 1 0 2 1 0 1 1 0 1 1 0 1 1 0 1 1 0 2 1 0 2 1 0 2 1 0 1 1 0 1 1 0 1 1 0 2 1 0 2 1 0 1 1 0 2 1 0 2 1 0 1 1 0 1 1 0 2 1 0 2 1 0 1 1...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok Accepted.
Test #19:
score: 7
Acceptable Answer
time: 3ms
memory: 100272kb
input:
50 37 420 2 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 57 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...
output:
5 4 3 2 1 33 34 35 36 37 6 32 7 31 8 30 9 29 10 27 28 11 26 12 25 13 24 14 23 15 22 16 21 17 20 18 19 -1 -1 -1 21 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 19 18 23 20 22 19 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 22 23 24 25 26 27 28 29 30 31 32 33 3...
result:
points 0.50 Partially Correct | type = 2
Test #20:
score: 7
Acceptable Answer
time: 3ms
memory: 103000kb
input:
20 90 206 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...
output:
-1 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 41 57 42 56 43 55 44 54 45 53 46 52 47 50 51 48 49 -1 45 44 43 42 41...
result:
points 0.50 Partially Correct | type = 2
Test #21:
score: 7
Acceptable Answer
time: 4ms
memory: 100540kb
input:
5 384 396 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...
output:
-1 187 183 182 181 180 179 178 177 176 175 174 173 172 171 170 169 168 167 166 165 164 163 162 161 160 159 158 157 156 155 154 153 152 151 150 149 148 147 146 145 144 143 142 141 140 139 138 137 136 135 134 133 132 131 130 129 128 127 126 125 124 123 122 121 120 119 118 117 116 115 114 113 112 111 1...
result:
points 0.50 Partially Correct | type = 2
Test #22:
score: 7
Acceptable Answer
time: 11ms
memory: 102820kb
input:
5 378 26744 2 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 ...
output:
190 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 ...
result:
points 0.50 Partially Correct | type = 2
Test #23:
score: 7
Acceptable Answer
time: 10ms
memory: 54460kb
input:
1 1934 290581 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 5...
output:
-1
result:
points 0.50 Partially Correct | type = 2
Test #24:
score: 14
Accepted
time: 4ms
memory: 102464kb
input:
1 1919 3856 2 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 ...
output:
956 955 954 953 952 951 950 949 948 947 946 945 944 943 942 941 940 939 938 937 936 935 934 933 932 931 930 929 928 927 926 925 924 923 922 921 920 919 918 917 916 915 914 913 912 911 910 909 908 907 906 905 904 903 902 901 900 899 898 897 896 895 894 893 892 891 890 889 888 887 886 885 884 883 882 ...
result:
ok Accepted.
Test #25:
score: 7
Acceptable Answer
time: 0ms
memory: 54784kb
input:
1 1835 1628390 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 ...
output:
-1
result:
points 0.50 Partially Correct | type = 2
Test #26:
score: 14
Accepted
time: 7ms
memory: 103948kb
input:
1 1854 642226 2 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 5...
output:
362 361 360 359 358 357 356 355 354 353 352 351 350 349 348 347 346 345 344 343 342 341 340 339 338 337 336 335 334 333 332 331 330 329 328 327 326 325 324 323 322 321 320 319 318 317 316 315 314 313 312 311 310 309 308 307 306 305 304 303 302 301 300 299 298 297 296 295 294 293 292 291 290 289 288 ...
result:
ok Accepted.
Subtask #5:
score: 0
Wrong Answer
Dependency #4:
50%
Acceptable Answer
Test #27:
score: 10
Accepted
time: 14ms
memory: 55036kb
input:
500000 1 0 1 1 0 2 1 0 2 1 0 1 1 0 2 1 0 2 1 0 2 1 0 2 1 0 2 1 0 2 1 0 2 1 0 2 1 0 1 1 0 1 1 0 1 1 0 1 1 0 2 1 0 2 1 0 2 1 0 1 1 0 2 1 0 2 1 0 1 1 0 1 1 0 2 1 0 1 1 0 2 1 0 2 1 0 2 1 0 1 1 0 1 1 0 2 1 0 2 1 0 2 1 0 2 1 0 2 1 0 2 1 0 2 1 0 2 1 0 2 1 0 1 1 0 1 1 0 2 1 0 2 1 0 2 1 0 2 1 0 1 1 0 1 1 0 2...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok Accepted.
Test #28:
score: 0
Wrong Answer
time: 42ms
memory: 125952kb
input:
5 93044 1765038246 2 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...
output:
-1 -1 -1 -1 -1
result:
wrong answer Wrong Answer.
Subtask #6:
score: 0
Runtime Error
Dependency #3:
50%
Acceptable Answer
Test #42:
score: 6
Acceptable Answer
time: 0ms
memory: 53988kb
input:
5 28 65 1 11 9 9 16 16 22 22 21 21 12 14 5 5 27 7 4 4 28 28 20 20 24 8 1 1 25 13 3 3 6 6 2 2 15 17 18 18 19 19 12 12 23 15 24 24 25 25 10 10 27 27 23 23 26 30 74 1 24 2 21 25 4 26 26 15 15 6 6 18 5 20 20 19 19 12 12 8 17 3 3 13 13 29 29 9 27 7 7 14 11 1 1 8 8 16 16 30 30 28 22 2 10 28 28 14 14 18 18...
output:
-1 -1 -1 -1 -1
result:
points 0.50 Partially Correct | type = 2
Test #43:
score: 12
Accepted
time: 0ms
memory: 103816kb
input:
5 27 286 2 22 12 25 2 2 15 15 3 20 16 13 26 27 10 10 21 21 1 1 23 19 24 24 4 4 7 7 26 26 6 6 3 3 18 18 23 11 8 8 9 9 14 14 17 17 12 12 16 16 23 23 5 27 51 2 11 18 18 19 12 10 10 2 4 3 3 5 15 23 23 6 6 9 22 7 26 24 24 13 13 14 14 2 25 7 16 20 20 19 19 17 17 8 1 7 8 2 2 9 9 7 7 5 5 27 27 21 29 56 2 29...
output:
-1 -1 5 13 6 22 11 17 2 16 23 27 4 29 3 15 18 21 14 20 28 26 1 19 25 7 8 10 9 24 12 -1 -1
result:
ok Accepted.
Test #44:
score: 12
Accepted
time: 0ms
memory: 54096kb
input:
5 1 0 1 1 0 1 1 0 2 1 0 1 1 0 2
output:
1 1 1 1 1
result:
ok Accepted.
Test #45:
score: 0
Runtime Error
input:
5 27 172 1 17 8 8 13 13 7 7 22 22 3 3 18 15 20 2 25 27 9 9 10 14 6 21 4 4 26 26 10 10 25 25 12 16 19 24 19 12 19 19 1 11 23 23 20 20 6 6 1 5 18 18 1 29 209 1 9 7 7 16 16 12 12 4 4 24 19 25 28 17 17 6 6 1 1 11 11 13 29 15 15 21 5 22 22 27 14 13 13 20 8 24 24 21 21 2 2 25 25 27 27 26 26 23 23 20 20 3 ...
output:
result:
Subtask #7:
score: 0
Skipped
Dependency #4:
50%
Acceptable Answer
Dependency #6:
0%
Subtask #8:
score: 0
Skipped
Dependency #7:
0%
Subtask #9:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
50%
Acceptable Answer
Dependency #3:
50%
Acceptable Answer
Dependency #4:
50%
Acceptable Answer
Dependency #5:
0%