QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#303375 | #7977. 彩虹航线 | hos_lyric | 100 ✓ | 1172ms | 78228kb | C++14 | 6.5kb | 2024-01-12 11:38:48 | 2024-01-12 11:38:48 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")
#include <chrono>
#ifdef LOCAL
mt19937_64 rng(58);
#else
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#endif
namespace bm {
constexpr int LIM_N0 = 210;
constexpr int LIM_N1 = 210;
constexpr int LIM_M = 40010;
int n0, n1, m, as[LIM_M], bs[LIM_M];
int to[LIM_N0], fr[LIM_N1], tof;
int pt[LIM_N0 + 2], zu[LIM_M], used[LIM_N0], lev[LIM_N0], que[LIM_N0], *qb, *qe;
void init(int n0_, int n1_) {
n0 = n0_; n1 = n1_; m = 0;
}
int ae(int u, int v) {
as[m] = u; bs[m] = v; return m++;
}
int augment(int u) {
used[u] = tof;
for (int j = pt[u]; j < pt[u + 1]; ++j) {
const int v = zu[j];
const int w = fr[v];
if (!~w || (used[w] != tof && lev[u] < lev[w] && augment(w))) {
to[u] = v; fr[v] = u; return 1;
}
}
return 0;
}
int run() {
memset(pt, 0, (n0 + 2) * sizeof(int));
for (int i = 0; i < m; ++i) ++pt[as[i] + 2];
for (int u = 2; u <= n0; ++u) pt[u + 1] += pt[u];
for (int i = 0; i < m; ++i) zu[pt[as[i] + 1]++] = bs[i];
memset(to, ~0, n0 * sizeof(int));
memset(fr, ~0, n1 * sizeof(int));
memset(used, ~0, n0 * sizeof(int));
for (tof = 0; ; ) {
qb = qe = que; memset(lev, ~0, n0 * sizeof(int));
for (int u = 0; u < n0; ++u) if (!~to[u]) lev[*qe++ = u] = 0;
for (; qb != qe; ) {
const int u = *qb++;
for (int j = pt[u]; j < pt[u + 1]; ++j) {
const int w = fr[zu[j]];
if (~w && !~lev[w]) lev[*qe++ = w] = lev[u] + 1;
}
}
int f = 0;
for (int u = 0; u < n0; ++u) if (!~to[u]) f += augment(u);
if (!f) return tof;
tof += f;
}
}
// s: true, t: false (s: reachable from unmatched left)
// vertex cover: (0: false, 0: true)
// independent set: (0: true, 1: false)
bool side0[LIM_N0], side1[LIM_N1];
void dfs(int u) {
if (!side0[u]) {
side0[u] = true;
for (int j = pt[u]; j < pt[u + 1]; ++j) {
const int v = zu[j];
if (!side1[v]) {
side1[v] = true;
const int w = fr[v];
if (~w) dfs(w);
}
}
}
}
void minCut() {
memset(side0, 0, n0 * sizeof(bool));
memset(side1, 0, n1 * sizeof(bool));
for (int u = 0; u < n0; ++u) if (!~to[u]) dfs(u);
}
} // namespace bm
int N, M, K;
vector<int> A, B;
vector<vector<int>> C;
int main() {
for (; ~scanf("%d%d%d", &N, &M, &K); ) {
A.resize(M);
B.resize(M);
C.assign(M, vector<int>(K));
for (int i = 0; i < M; ++i) {
scanf("%d%d", &A[i], &B[i]);
--A[i];
--B[i];
for (int k = 0; k < K; ++k) {
scanf("%d", &C[i][k]);
}
}
vector<int> degA(N, 0), degB(N, 0);
for (int i = 0; i < M; ++i) {
++degA[A[i]];
++degB[B[i]];
}
for (int u = 0, v = 0; ; ) {
for (; u < N && degA[u] >= K; ++u) {}
for (; v < N && degB[v] >= K; ++v) {}
if (u == N && v == N) break;
assert(u < N);
assert(v < N);
A.push_back(u);
B.push_back(v);
C.emplace_back();
for (int k = 0; k < K; ++k) C.back().push_back(k);
++degA[u];
++degB[v];
}
const int MM = A.size();
// cerr<<"A = "<<A<<", B = "<<B<<", C = "<<C<<endl;
assert(degA == vector<int>(N, K));
assert(degB == vector<int>(N, K));
vector<int> colors(MM, -1);
for (int k = 0; k < K; ++k) {
bm::init(N, N);
for (int i = 0; i < MM; ++i) if (!~colors[i]) {
bm::ae(A[i], B[i]);
}
const int flow = bm::run();
assert(flow == N);
for (int i = 0; i < MM; ++i) if (!~colors[i]) {
if (bm::to[A[i]] == B[i]) {
// !
bm::to[A[i]] = -1;
colors[i] = k;
}
}
}
// cerr<<"colors = "<<colors<<endl;
int limC = 0;
for (int i = 0; i < MM; ++i) {
for (int k = 0; k < K; ++k) {
chmax(limC, C[i][k]);
}
}
++limC;
vector<vector<int>> iss(limC);
for (int i = 0; i < MM; ++i) {
for (int k = 0; k < K; ++k) {
iss[C[i][k]].push_back(i);
}
}
vector<int> ans(MM, -1);
for (int c = 0; c < limC; ++c) if (iss[c].size()) {
/*
stable matching
left: prefer large color
right: prefer small color
*/
vector<vector<int>> g(N);
for (const int i : iss[c]) if (!~ans[i]) {
g[A[i]].push_back(i);
}
for (int u = 0; u < N; ++u) {
sort(g[u].begin(), g[u].end(), [&](int i0, int i1) -> bool {
return (colors[i0] < colors[i1]);
});
}
vector<int> isA(N, -1), isB(N, -1);
for (int u0 = 0; u0 < N; ++u0) {
for (int u = u0; g[u].size(); ) {
const int i = g[u].back();
g[u].pop_back();
if (~isB[B[i]]) {
if (colors[isB[B[i]]] > colors[i]) {
u = A[isB[B[i]]];
isA[A[i]] = isB[B[i]] = i;
isA[u] = -1;
}
} else {
isA[A[i]] = isB[B[i]] = i;
break;
}
}
}
// cerr<<c<<": "<<isA<<" "<<isB<<endl;
for (int u = 0; u < N; ++u) if (~isA[u]) {
ans[isA[u]] = c;
}
}
for (int i = 0; i < M; ++i) {
if (i) printf(" ");
printf("%d", ans[i]);
}
puts("");
}
return 0;
}
詳細信息
Subtask #1:
score: 1
Accepted
Test #1:
score: 1
Accepted
time: 1ms
memory: 4060kb
input:
150 150 1 144 5 1 141 54 1 26 120 1 148 68 1 136 62 1 114 1 1 33 136 1 85 100 1 97 124 1 84 66 1 107 81 1 82 135 1 112 44 1 20 89 1 50 32 1 52 94 1 89 88 1 3 57 1 130 23 1 140 150 1 96 37 1 122 38 1 41 63 1 99 85 1 13 95 1 142 47 1 95 4 1 69 17 1 27 119 1 73 93 1 108 43 1 54 18 1 37 76 1 67 114 1 40...
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 construction is correct.
Test #2:
score: 0
Accepted
time: 1ms
memory: 3900kb
input:
150 150 1 117 132 96 147 4 114 67 57 60 62 94 20 48 117 68 31 144 27 19 44 121 3 51 92 83 52 67 26 125 56 8 124 75 125 31 52 79 8 21 132 14 136 77 111 45 134 136 145 129 73 85 122 92 143 59 76 36 60 127 115 102 126 133 10 106 32 93 35 106 75 47 102 45 140 41 44 108 146 25 98 106 140 116 76 143 3 87 ...
output:
96 114 60 20 68 27 121 92 67 56 75 52 21 136 45 145 85 143 36 115 133 32 106 102 41 146 106 76 87 90 116 15 147 51 35 85 15 83 43 105 89 12 89 140 103 114 135 78 93 80 87 93 19 7 125 132 96 96 99 48 1 63 3 6 146 116 48 9 126 6 106 64 74 84 16 23 119 51 7 83 96 56 94 97 27 15 51 106 95 32 70 103 75 8...
result:
ok construction is correct.
Test #3:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
150 10 1 35 145 1 145 88 2 130 14 1 111 142 1 138 99 1 76 73 1 101 79 1 147 137 2 65 64 1 108 8 2
output:
1 2 1 1 1 1 1 2 1 2
result:
ok construction is correct.
Subtask #2:
score: 2
Accepted
Test #4:
score: 2
Accepted
time: 400ms
memory: 53924kb
input:
75 5625 150 11 6 680849 150419 731361 419631 223710 806977 837589 529911 568337 456216 515190 302854 672904 388629 548276 803173 770491 610684 550790 786097 253610 446581 705772 610053 637171 567249 365794 571846 431219 213414 466432 53255 748825 765338 761154 556712 159152 463622 706471 49434 59624...
output:
980 3381 1885 123 19436 2560 2359 3518 22349 781 3686 5196 6995 2979 7370 631 7775 5611 9896 1481 11434 2253 2756 170 1112 7853 9236 20266 5409 1781 3095 1124 2145 201 8611 430 3048 1838 129 7881 9615 12237 335 425 9372 303 4913 1877 16645 6954 5793 1073 6631 8819 4794 1400 11886 3472 2148 3635 2287...
result:
ok construction is correct.
Test #5:
score: 0
Accepted
time: 77ms
memory: 22444kb
input:
75 5625 150 55 59 136 110 80 141 34 72 121 2 116 38 39 16 56 20 147 81 58 64 24 83 73 30 127 97 128 35 77 96 54 21 106 57 32 115 133 84 50 103 94 45 68 53 31 8 55 44 89 41 36 150 3 28 9 98 66 49 119 101 114 112 82 11 22 124 134 107 105 90 88 145 87 135 26 79 37 122 10 15 104 27 18 120 7 13 46 139 40...
output:
147 140 149 145 146 135 149 149 149 146 149 149 149 149 148 143 149 142 146 149 149 148 148 147 142 149 147 149 148 146 149 149 148 149 149 148 149 149 149 148 144 149 111 148 149 149 142 149 144 146 148 141 144 143 149 148 149 149 149 149 148 146 148 148 146 98 147 147 147 147 139 149 147 149 147 1...
result:
ok construction is correct.
Test #6:
score: 0
Accepted
time: 266ms
memory: 43152kb
input:
75 3750 150 1 29 15545 372923 77579 125076 509966 151564 332286 414939 296369 227609 9580 52174 99587 224186 2679 309545 38096 115252 281893 44718 259941 187595 500086 197842 267668 399469 254416 114691 268905 112134 257669 210411 135373 423915 537194 17707 204354 99757 234452 307155 82087 64190 309...
output:
1133 8931 6979 292 4622 3682 3085 1837 3717 806 1577 243 3800 1530 5699 5036 5663 1854 1290 447 377 7910 1190 5340 9940 4996 13835 5304 878 5407 8178 3666 2542 478 281 3939 1330 449 6141 312 4935 2216 2337 3905 6700 807 1509 776 23474 11235 10940 9509 5258 10608 7340 556 3767 3414 1978 748 6728 4270...
result:
ok construction is correct.
Test #7:
score: 0
Accepted
time: 66ms
memory: 22644kb
input:
75 3750 150 43 71 86 127 132 6 139 123 83 37 85 103 52 102 4 148 111 34 110 66 42 130 150 149 53 45 137 129 2 5 87 79 146 47 9 98 96 54 17 126 81 115 7 105 117 119 101 144 74 23 44 19 84 97 50 13 22 94 78 63 134 40 142 76 109 95 12 138 112 72 136 24 77 31 32 118 124 135 68 104 16 1 93 106 128 51 20 ...
output:
147 149 145 147 149 142 149 144 143 141 149 149 148 143 141 149 149 139 149 140 149 149 147 149 148 149 149 149 149 149 144 145 148 149 149 145 148 149 141 149 148 133 149 141 149 144 149 148 148 147 147 149 149 145 146 144 143 148 146 149 146 132 148 149 148 135 134 148 139 149 149 149 147 145 147 ...
result:
ok construction is correct.
Subtask #3:
score: 11
Accepted
Test #8:
score: 11
Accepted
time: 1ms
memory: 3844kb
input:
150 300 2 81 6 1 2 64 88 1 2 5 76 2 1 22 9 2 1 32 142 1 2 97 32 2 1 18 87 1 2 146 100 2 1 56 139 1 2 61 109 2 1 124 105 2 1 126 145 1 2 16 19 1 2 16 138 2 1 131 111 2 1 145 111 2 1 59 59 2 1 89 43 1 2 2 38 1 2 63 149 2 1 46 48 1 2 140 131 1 2 86 10 2 1 116 40 1 2 123 38 2 1 75 109 2 1 131 142 1 2 9 ...
output:
2 2 2 2 2 1 2 2 1 2 1 1 1 2 2 1 1 2 2 1 1 1 1 2 1 1 1 1 2 1 1 2 2 2 2 2 1 1 2 1 1 2 1 1 2 2 1 2 2 2 2 1 1 1 1 1 2 1 2 2 2 1 2 1 1 2 1 1 2 1 1 1 1 2 2 2 1 2 1 2 2 1 2 1 2 1 1 1 2 1 1 1 1 2 2 1 2 1 1 1 2 1 2 1 2 2 2 1 2 2 2 2 2 1 2 1 1 2 1 2 1 1 2 2 1 2 1 2 1 1 2 2 2 2 2 2 1 1 2 1 2 2 2 2 2 1 2 1 2 2 ...
result:
ok construction is correct.
Test #9:
score: 0
Accepted
time: 1ms
memory: 3892kb
input:
150 300 2 60 122 3 1 114 17 2 1 21 19 3 1 134 75 3 1 64 81 2 1 52 33 1 3 45 27 1 2 148 91 2 1 110 100 1 2 100 74 2 3 53 130 3 2 59 19 3 1 149 108 3 1 19 92 1 3 85 66 3 2 80 89 3 2 16 4 2 3 39 90 2 3 53 102 3 1 20 21 3 1 21 112 1 3 76 98 1 2 7 130 3 1 140 129 2 3 139 100 3 1 127 77 1 3 136 113 3 2 54...
output:
3 1 3 1 1 1 2 2 1 3 2 1 3 3 2 2 3 2 1 3 1 1 1 2 3 3 2 2 2 2 1 2 2 1 3 1 2 1 1 2 2 1 3 3 2 1 2 1 1 3 1 1 3 1 1 2 1 2 1 1 3 2 1 3 1 2 3 2 1 2 2 3 1 1 1 1 1 3 3 3 2 3 1 3 1 1 1 2 1 2 1 3 1 1 3 1 3 1 1 2 1 3 2 2 1 2 2 2 3 2 2 2 2 2 2 1 3 2 2 2 3 1 2 1 2 2 3 2 1 1 2 2 2 1 2 2 3 3 3 2 1 3 1 2 2 3 2 1 3 1 ...
result:
ok construction is correct.
Test #10:
score: 0
Accepted
time: 1ms
memory: 3788kb
input:
150 300 2 27 132 4 3 36 120 3 4 100 77 2 3 139 62 2 1 106 59 2 3 33 69 2 3 111 14 4 2 90 140 1 2 38 63 2 4 76 49 1 4 49 26 4 2 50 100 2 4 116 7 3 4 143 127 3 4 43 105 3 1 65 72 3 4 94 111 1 2 70 72 1 2 49 107 3 2 92 27 4 2 42 119 4 1 42 46 2 1 88 143 4 3 79 99 2 3 3 84 4 1 85 13 4 2 38 67 1 3 43 31 ...
output:
4 3 2 1 2 2 4 1 4 1 4 2 3 3 1 4 1 1 2 4 4 1 3 2 4 2 1 2 3 4 3 1 1 2 3 4 3 1 1 4 2 2 1 1 1 1 1 1 2 1 1 2 1 4 3 3 4 2 1 1 2 2 1 2 4 1 1 2 4 1 2 2 1 1 2 2 1 2 1 3 3 3 2 2 2 3 3 2 1 4 2 1 3 3 2 3 1 3 2 1 1 2 4 2 3 4 3 2 3 3 3 1 1 2 1 3 4 2 3 1 1 2 1 2 2 3 2 3 3 4 2 1 1 4 3 2 4 3 2 3 1 4 3 1 3 1 4 2 1 4 ...
result:
ok construction is correct.
Test #11:
score: 0
Accepted
time: 1ms
memory: 4088kb
input:
150 300 2 87 61 2 16 114 49 13 10 25 34 13 18 19 62 2 6 44 60 10 14 132 71 20 18 40 51 13 17 67 25 13 18 125 40 19 14 82 53 19 8 66 118 19 3 38 136 6 12 150 135 14 7 75 53 10 1 54 33 4 8 69 19 8 5 129 72 13 17 149 74 14 10 136 117 1 18 13 80 4 18 107 11 13 18 41 14 3 10 15 90 3 11 104 43 6 18 52 80 ...
output:
2 10 13 2 14 18 13 13 14 8 3 6 7 1 4 5 13 10 1 4 13 3 3 6 6 12 14 2 18 2 16 16 10 6 10 6 9 3 7 5 14 8 3 3 4 3 2 12 6 16 5 1 7 4 4 9 19 6 11 2 16 4 8 1 14 1 4 14 1 2 8 8 6 10 2 2 6 2 2 4 1 4 11 16 18 12 2 18 12 4 7 18 8 11 11 5 6 11 5 9 4 3 1 12 10 7 3 17 2 19 6 1 6 1 10 12 1 7 13 5 2 12 8 10 5 13 14...
result:
ok construction is correct.
Test #12:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
150 300 2 46 114 441 328 119 80 69 102 9 78 444 336 8 47 230 59 60 140 548 248 147 131 36 399 68 86 447 183 97 13 461 318 31 93 536 570 35 41 237 149 53 77 156 95 123 119 562 202 94 26 519 23 129 128 438 80 74 139 454 108 92 68 559 399 140 61 11 178 106 137 15 575 140 15 22 289 65 50 263 546 9 45 31...
output:
328 69 336 59 248 36 183 318 536 149 95 202 23 80 108 399 11 15 22 263 31 195 67 207 27 283 367 230 30 535 547 302 287 41 297 110 260 168 239 90 185 137 83 295 29 51 12 264 277 299 15 453 167 154 150 197 46 368 427 154 453 463 458 172 299 496 253 203 301 106 113 168 101 34 429 155 172 247 263 110 29...
result:
ok construction is correct.
Test #13:
score: 0
Accepted
time: 1ms
memory: 4100kb
input:
150 150 2 138 25 1 2 71 40 2 1 146 116 1 2 110 122 2 1 59 36 1 2 147 145 2 1 80 88 2 1 38 13 1 2 137 6 1 2 57 84 2 1 25 84 2 1 125 75 2 1 73 128 1 2 94 69 2 1 27 18 1 2 89 119 1 2 8 131 1 2 62 3 1 2 32 67 2 1 77 77 2 1 78 6 1 2 142 70 2 1 61 16 2 1 21 129 2 1 2 126 1 2 136 128 1 2 141 35 2 1 65 78 1...
output:
2 1 2 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 2 1 2 2 1 2 2 1 2 1 2 2 1 2 1 1 2 1 2 1 2 1 2 1 2 1 1 2 1 2 2 2 2 1 1 2 2 2 2 2 2 1 1 1 1 1 2 2 1 1 2 2 2 1 2 1 2 1 2 2 2 1 2 1 2 2 2 2 1 2 1 2 2 1 1 1 2 2 1 2 1 1 1 2 1 2 1 2 1 2 1 2 2 1 2 1 2 1 2 2 2 1 2 2 2 1 2 1 1 1 1 1 1 1 2 1 2 2 2 2 2 1 1 1 1 2 2 1 2 2
result:
ok construction is correct.
Test #14:
score: 0
Accepted
time: 1ms
memory: 3816kb
input:
150 150 2 73 97 3 2 50 90 3 1 106 133 1 3 2 65 1 2 47 141 3 2 75 24 1 2 93 85 2 1 14 12 3 2 53 15 2 1 136 120 1 3 68 49 1 2 13 127 2 3 26 87 1 3 78 79 1 3 130 97 3 1 3 8 3 1 55 3 3 1 122 27 3 1 39 51 2 3 72 64 2 3 85 98 2 1 148 18 2 1 90 110 3 1 21 89 2 1 116 75 1 2 52 99 1 2 41 29 1 3 60 130 2 1 10...
output:
2 3 1 1 2 2 2 2 1 3 2 2 1 1 1 1 3 3 3 2 1 1 1 2 1 1 1 1 1 2 1 1 2 3 1 1 2 2 2 3 3 3 2 2 1 2 3 2 2 1 1 1 2 2 1 2 2 2 2 1 2 1 1 3 2 3 2 3 2 3 2 3 1 2 2 2 2 2 2 2 2 2 3 1 1 2 3 1 2 3 2 2 2 2 1 1 1 1 1 2 1 1 2 2 1 2 2 3 2 1 3 1 1 1 2 1 1 3 1 1 2 3 2 2 1 2 2 2 2 3 3 2 2 1 1 3 3 2 2 3 1 1 3 2 2 1 1 2 3 3
result:
ok construction is correct.
Test #15:
score: 0
Accepted
time: 1ms
memory: 3844kb
input:
150 150 2 134 2 3 4 139 116 2 4 100 69 1 4 45 66 4 2 24 64 2 3 93 43 4 2 137 144 1 3 40 105 1 4 134 108 2 4 98 40 3 1 20 144 3 1 11 51 3 2 101 89 1 3 46 53 1 2 39 23 1 3 109 40 2 3 30 7 2 3 142 6 1 3 38 112 4 2 108 28 1 2 111 32 1 4 28 49 4 2 89 14 2 4 65 143 4 3 43 8 1 2 92 56 4 2 106 53 2 4 117 14...
output:
3 2 4 2 2 2 3 4 2 1 1 2 3 2 1 2 2 1 2 1 1 2 2 3 1 4 4 2 1 2 4 3 1 4 2 3 4 2 3 2 1 2 2 2 3 4 1 2 3 4 3 3 3 4 2 2 2 2 2 4 1 1 1 1 3 1 1 1 2 2 2 1 4 2 1 2 1 2 2 2 2 2 2 3 2 3 3 2 3 3 3 2 4 2 3 1 1 3 4 1 3 2 3 2 1 1 4 3 1 2 2 2 2 1 1 3 3 2 3 3 2 2 4 2 1 4 3 1 1 2 4 3 1 3 2 2 2 4 2 1 1 2 3 1 1 4 1 2 1 4
result:
ok construction is correct.
Test #16:
score: 0
Accepted
time: 1ms
memory: 4100kb
input:
150 150 2 42 118 2 5 44 13 7 14 95 7 20 11 92 142 11 19 96 150 10 18 11 52 6 18 66 48 1 13 17 5 13 16 91 22 8 20 19 71 15 6 73 61 10 5 50 63 3 14 101 143 20 5 52 114 12 17 111 60 19 9 20 4 6 7 54 63 16 18 31 31 9 4 33 148 10 8 37 32 17 19 60 57 20 8 31 136 8 1 65 87 19 4 138 72 6 17 71 112 8 20 83 3...
output:
2 7 11 19 10 6 13 13 8 6 10 3 5 12 9 6 16 4 8 17 8 1 4 6 8 2 2 6 2 8 7 9 2 19 9 1 1 12 9 10 11 1 15 6 9 4 18 3 13 2 13 9 5 8 12 8 10 8 5 16 18 9 6 11 4 16 6 3 11 16 5 8 1 16 5 4 5 2 14 7 8 7 9 7 6 8 1 16 5 7 19 8 1 12 12 11 12 5 3 14 1 10 8 5 6 5 8 10 9 3 15 16 9 4 3 18 10 3 3 6 11 3 7 11 9 3 6 16 5...
result:
ok construction is correct.
Test #17:
score: 0
Accepted
time: 1ms
memory: 4116kb
input:
150 150 2 137 126 61 39 96 140 224 95 145 72 296 11 23 92 241 36 98 129 102 20 90 41 85 39 41 113 188 148 93 131 282 107 10 76 23 225 8 16 16 124 115 135 270 30 20 129 88 48 110 125 94 272 101 98 56 238 106 116 125 110 73 138 234 193 22 127 245 8 58 29 8 140 86 36 212 170 40 97 288 204 30 50 109 75 ...
output:
39 95 11 36 20 39 148 107 23 16 30 48 94 56 110 193 8 8 170 204 75 250 1 221 200 108 92 71 94 73 87 43 88 43 30 32 215 138 51 82 216 12 3 9 227 6 67 32 127 114 11 190 25 97 55 104 14 42 84 167 114 151 99 132 174 164 102 56 134 145 2 167 15 149 26 21 138 112 47 128 87 93 144 74 126 208 67 37 208 265 ...
result:
ok construction is correct.
Subtask #4:
score: 37
Accepted
Test #18:
score: 37
Accepted
time: 232ms
memory: 35920kb
input:
149 22201 150 106 24 20 90 56 109 85 33 76 25 97 77 134 75 15 24 88 16 93 126 43 94 116 120 28 130 21 140 70 111 71 32 29 41 132 39 84 62 27 92 55 117 129 125 127 104 74 114 14 145 36 121 22 69 68 133 59 65 58 148 131 40 54 118 110 3 61 105 4 112 142 122 73 37 1 113 45 87 57 89 103 98 100 63 146 106...
output:
146 149 149 137 149 148 113 149 148 141 143 142 149 149 149 148 149 124 149 146 147 145 149 149 149 149 148 148 148 149 149 149 144 147 149 143 149 149 146 149 148 149 147 135 148 149 130 145 147 148 149 148 149 149 118 149 140 148 144 149 143 148 148 148 148 140 149 147 131 145 149 148 147 149 145 ...
result:
ok construction is correct.
Test #19:
score: 0
Accepted
time: 233ms
memory: 36064kb
input:
149 22201 150 59 87 57 143 9 144 61 104 129 116 26 50 73 24 138 78 82 137 4 100 81 69 101 140 102 115 149 18 42 54 16 28 75 74 130 70 35 12 29 36 2 121 62 37 21 64 71 133 110 96 58 67 59 128 124 56 106 103 53 107 49 141 90 105 8 1 65 13 146 77 83 22 134 84 108 119 44 15 32 88 17 79 48 33 46 120 111 ...
output:
148 148 147 143 80 149 147 148 149 149 148 149 136 145 148 147 147 148 148 146 149 149 147 149 141 149 145 147 147 149 149 147 149 144 147 149 149 149 147 134 148 149 149 148 149 149 147 131 148 148 148 149 135 146 149 137 146 141 146 149 149 149 149 137 121 145 148 148 147 149 146 146 147 149 147 1...
result:
ok construction is correct.
Test #20:
score: 0
Accepted
time: 221ms
memory: 35684kb
input:
149 22201 150 85 67 67 47 152 75 90 126 113 128 46 30 36 85 21 97 79 16 61 39 120 99 153 105 76 107 56 116 118 119 122 94 9 127 12 15 68 104 80 7 100 146 125 95 53 112 74 143 81 27 1 52 40 71 29 88 139 69 13 11 92 132 45 42 38 151 3 60 24 91 2 25 86 133 41 10 33 135 82 57 110 6 114 140 138 62 87 64 ...
output:
141 143 149 143 149 149 148 147 146 148 149 122 129 135 126 148 150 149 148 145 149 148 145 139 149 140 139 148 148 148 142 149 148 79 145 148 148 136 149 134 148 147 146 147 147 149 145 149 125 124 144 148 149 146 148 121 99 148 149 147 146 148 141 149 146 135 148 149 146 144 149 145 145 142 139 14...
result:
ok construction is correct.
Test #21:
score: 0
Accepted
time: 222ms
memory: 37004kb
input:
149 22201 150 20 14 155 45 96 11 71 74 38 143 146 165 31 128 56 133 137 127 4 75 108 44 69 77 141 55 113 22 163 54 67 29 23 37 63 148 25 117 97 65 89 76 51 112 139 151 109 66 82 114 13 80 73 119 61 84 53 40 156 24 20 164 50 122 124 158 8 118 7 120 160 154 152 145 46 138 30 162 132 16 59 15 91 94 52 ...
output:
145 145 148 149 146 140 147 149 148 147 147 147 144 146 148 146 146 141 145 147 149 146 135 143 148 145 137 145 145 145 143 150 145 147 145 147 146 149 146 121 148 146 145 149 147 148 133 142 148 137 145 145 149 148 147 145 149 149 138 146 125 150 148 147 137 147 141 150 147 143 147 146 142 145 143 ...
result:
ok construction is correct.
Test #22:
score: 0
Accepted
time: 1160ms
memory: 77940kb
input:
149 22201 150 64 32 323179 933179 87351 997262 611605 404909 732640 452641 642757 539724 945803 438567 594564 413639 542011 13240 428009 469975 976134 998911 916345 580907 215711 24916 933666 193524 159822 766638 161868 151754 502972 194801 55497 466348 151018 849178 317067 34382 293653 929582 83436...
output:
13240 10115 23541 7973 13512 1703 3512 11086 1773 8255 5157 6137 7545 503 327 6820 3506 7744 2089 2811 8484 27220 14708 20666 3855 258 5632 21768 7518 7739 6790 7815 17629 46 1011 935 14569 4481 2399 436 15743 3747 1670 1884 2078 4887 17294 18388 11942 33 2787 7929 2221 16236 10913 5765 201 7063 620...
result:
ok construction is correct.
Subtask #5:
score: 21
Accepted
Test #23:
score: 21
Accepted
time: 229ms
memory: 35924kb
input:
150 22500 150 117 116 91 74 113 95 110 26 141 115 38 66 71 138 17 83 112 99 149 18 3 44 15 28 53 114 96 37 7 145 20 109 80 19 117 16 63 27 42 137 135 132 14 39 1 148 147 30 68 126 12 32 57 67 119 139 124 46 133 24 36 51 69 88 131 60 86 140 102 29 100 150 35 123 84 85 90 105 75 45 77 143 130 127 98 7...
output:
150 150 148 148 150 149 149 150 125 149 150 142 148 148 148 150 134 150 149 142 150 150 150 150 143 149 149 150 148 149 145 111 150 149 149 150 148 150 141 150 148 150 150 150 150 150 150 145 150 149 149 150 150 149 150 148 150 147 150 150 143 150 149 146 150 150 147 150 150 146 147 142 113 147 149 ...
result:
ok construction is correct.
Test #24:
score: 0
Accepted
time: 232ms
memory: 35776kb
input:
150 22500 150 147 68 107 8 61 49 133 15 148 55 122 84 72 75 29 19 118 99 51 79 142 117 11 50 149 69 87 45 73 92 41 110 56 144 128 47 77 78 141 48 31 53 136 103 94 26 145 151 121 46 101 58 38 10 102 126 22 140 138 40 129 96 82 150 95 30 27 100 28 13 114 74 81 52 116 17 4 143 66 90 20 2 111 21 7 91 68...
output:
107 150 150 82 137 149 149 144 146 148 150 142 142 149 105 149 149 148 149 148 148 149 150 148 135 124 139 148 150 148 146 144 150 150 149 148 148 149 150 144 148 150 148 148 150 150 148 149 147 147 149 149 148 150 149 149 125 150 137 150 150 149 150 147 148 148 139 148 148 144 138 150 150 148 146 1...
result:
ok construction is correct.
Test #25:
score: 0
Accepted
time: 229ms
memory: 35952kb
input:
150 22500 150 53 59 70 142 54 108 56 6 22 92 39 80 38 84 125 144 117 127 74 71 40 140 33 146 145 72 85 44 128 45 86 94 93 66 34 52 21 59 57 137 78 120 63 67 13 124 2 126 60 76 79 102 116 100 23 150 58 115 107 82 104 138 97 151 106 131 152 42 132 77 32 11 89 55 30 31 95 49 65 96 141 135 17 114 143 14...
output:
150 146 149 106 150 150 150 147 146 149 148 149 131 148 148 149 150 147 147 150 147 150 149 149 149 150 150 149 149 146 146 147 144 148 142 145 147 144 101 122 148 149 148 150 139 150 150 149 150 149 149 143 147 147 149 131 149 150 150 150 149 147 144 150 116 149 147 150 150 146 143 136 148 145 150 ...
result:
ok construction is correct.
Test #26:
score: 0
Accepted
time: 227ms
memory: 35948kb
input:
150 22500 150 81 87 83 67 109 57 147 69 102 72 25 29 39 94 56 73 27 41 81 53 144 101 135 117 127 96 5 145 155 22 87 106 38 19 14 86 58 97 20 35 65 124 47 93 50 10 75 80 52 31 76 154 126 78 91 113 42 118 9 115 15 51 149 141 119 134 92 74 64 129 66 103 110 49 85 143 133 148 12 61 142 151 131 153 21 34...
output:
145 148 146 150 121 148 150 149 149 148 148 148 148 146 149 149 146 145 145 145 150 147 150 144 148 145 150 146 149 147 150 150 151 148 146 146 150 122 149 146 149 149 150 150 148 150 144 148 138 148 146 150 146 148 150 145 149 146 146 149 150 138 145 147 150 148 146 148 34 146 150 150 148 145 149 1...
result:
ok construction is correct.
Test #27:
score: 0
Accepted
time: 222ms
memory: 37356kb
input:
150 22500 150 21 135 30 53 162 62 34 163 112 104 16 67 48 161 137 99 94 93 158 20 70 91 12 148 40 24 141 131 29 132 14 44 31 7 167 146 35 113 45 39 136 84 142 108 87 123 129 85 58 134 5 166 28 73 128 56 80 147 155 6 149 76 41 36 88 66 121 86 168 97 63 47 26 116 169 151 95 15 100 19 50 103 98 126 38 ...
output:
147 147 148 144 148 150 150 146 149 150 72 119 150 148 150 140 148 146 144 150 149 146 145 146 147 123 130 149 144 117 151 151 150 148 117 124 147 150 148 149 148 142 148 148 148 149 145 146 149 147 148 136 144 135 150 146 149 146 149 146 148 149 148 141 151 122 131 150 149 149 150 146 150 150 147 1...
result:
ok construction is correct.
Test #28:
score: 0
Accepted
time: 1172ms
memory: 78228kb
input:
150 22500 150 142 84 95127 811376 352518 34572 172491 645409 426070 585385 839136 465937 516075 461423 149284 929627 554965 743036 475305 268781 574670 840165 214086 131675 655651 402556 295405 797734 729790 132978 283490 807542 165311 188276 808619 466578 568749 15488 450230 528624 262879 824125 58...
output:
100 15190 7303 17063 13592 2419 658 385 3163 5545 17208 9676 462 6548 7810 1548 1070 1324 26648 2921 10551 3953 6646 8367 14836 9873 2723 6488 8060 10247 9394 9983 14260 371 974 11797 4944 18851 6570 8901 2229 1182 19219 6745 4575 29630 15348 758 1085 9021 4974 12386 26035 19589 3754 12063 1421 1144...
result:
ok construction is correct.
Subtask #6:
score: 28
Accepted
Test #29:
score: 28
Accepted
time: 1ms
memory: 3996kb
input:
150 450 3 57 22 2 1 3 142 57 1 3 2 138 113 3 1 2 13 77 2 3 1 43 112 1 2 3 82 99 2 1 3 66 65 3 1 2 3 31 2 1 3 24 146 3 2 1 127 18 2 3 1 125 37 1 2 3 13 137 1 2 3 105 127 1 3 2 54 20 1 2 3 48 15 3 1 2 23 71 2 3 1 30 28 1 2 3 125 146 1 3 2 68 120 2 1 3 38 92 2 1 3 101 100 1 3 2 81 28 1 3 2 70 7 1 2 3 1...
output:
3 2 2 3 2 3 3 3 3 1 3 2 1 1 2 2 1 2 3 3 2 3 3 2 2 3 3 1 1 2 3 1 2 1 2 3 1 1 1 3 3 1 2 3 1 1 3 3 1 3 3 2 3 3 3 3 3 1 2 3 2 1 1 1 2 3 3 2 3 2 3 3 3 3 1 1 1 2 1 2 1 3 3 2 2 2 2 3 3 2 3 3 3 3 3 1 1 2 1 2 2 1 3 1 3 3 2 2 1 3 1 1 1 3 3 3 1 1 3 3 3 3 1 3 3 3 2 2 3 3 3 2 1 2 3 2 3 1 2 2 3 2 1 2 1 1 2 3 2 2 ...
result:
ok construction is correct.
Test #30:
score: 0
Accepted
time: 1ms
memory: 3884kb
input:
150 450 3 148 73 905 1007 1204 72 13 614 952 114 72 3 1026 931 764 33 21 1143 204 536 19 112 694 1261 734 104 68 1057 72 1249 83 66 311 147 656 141 5 1349 1317 700 12 113 331 375 1165 49 7 1114 1149 1224 79 41 531 46 712 128 20 630 1175 399 35 74 421 1148 608 57 124 840 108 1238 63 22 922 403 203 35...
output:
905 114 764 204 694 72 147 700 331 1114 46 399 421 108 203 5 223 132 98 676 134 203 42 31 341 976 822 798 64 94 212 266 374 384 52 708 990 76 249 492 130 313 529 89 46 681 15 460 911 833 194 395 104 617 308 122 50 405 38 776 49 25 41 1067 106 986 146 523 366 290 757 103 575 873 100 467 153 211 762 4...
result:
ok construction is correct.
Test #31:
score: 0
Accepted
time: 1ms
memory: 3920kb
input:
150 450 3 111 66 3 4 1 62 51 3 2 4 117 58 3 4 1 54 105 1 3 4 40 108 3 1 4 104 112 2 4 1 131 73 4 3 1 109 30 1 4 3 36 130 3 4 2 40 70 2 3 1 24 112 3 1 4 44 119 4 1 2 39 91 1 4 3 28 118 1 2 3 8 117 2 4 1 110 109 3 1 4 99 20 4 1 2 131 49 4 1 2 130 114 1 4 3 133 57 3 1 2 41 125 1 3 4 21 65 1 2 3 144 143...
output:
4 2 1 1 3 1 1 1 3 2 3 4 4 1 1 1 2 4 3 1 1 2 1 2 1 4 3 2 1 1 3 1 2 2 2 3 2 2 3 3 3 4 2 1 1 2 1 4 1 2 4 1 2 1 3 1 3 2 2 3 1 1 1 2 4 2 1 1 3 1 3 1 3 4 4 3 1 4 4 2 4 3 2 3 2 2 3 2 2 2 1 3 2 3 1 3 3 3 4 3 4 1 2 1 3 1 2 4 1 2 4 1 2 1 4 2 2 2 3 1 3 1 1 4 4 4 1 1 1 4 4 3 3 2 1 1 1 3 3 2 2 3 1 4 4 1 2 1 2 2 ...
result:
ok construction is correct.
Test #32:
score: 0
Accepted
time: 1ms
memory: 4140kb
input:
150 450 3 79 108 4 7 3 85 72 8 3 7 105 47 5 2 8 56 47 3 4 5 66 90 7 5 3 109 68 8 1 7 84 73 5 2 3 14 7 8 5 6 129 111 5 1 2 103 45 1 6 7 102 96 7 3 2 30 80 6 1 8 22 80 5 1 6 55 21 6 3 5 4 104 6 3 8 27 130 2 1 3 64 109 7 2 4 20 110 7 8 6 5 50 5 8 2 116 8 7 8 6 5 74 3 1 6 86 124 2 4 7 129 57 2 7 8 2 9 2...
output:
3 3 8 4 3 1 5 5 1 1 7 6 5 3 3 1 4 6 2 6 1 2 2 7 3 2 2 2 4 5 3 6 6 4 6 2 3 1 4 1 1 2 3 2 1 2 6 1 4 3 7 4 3 1 2 6 6 2 2 1 2 6 1 1 6 1 6 1 1 1 4 4 5 4 2 1 4 2 1 5 3 5 4 4 2 2 1 3 3 2 5 1 3 2 4 8 4 5 1 4 4 2 3 1 1 6 4 5 3 1 2 6 2 1 5 1 3 2 6 3 2 2 3 1 5 2 8 1 1 3 5 7 3 4 1 6 2 1 3 2 6 1 2 3 1 3 7 1 1 2 ...
result:
ok construction is correct.
Test #33:
score: 0
Accepted
time: 0ms
memory: 3924kb
input:
150 350 3 69 53 1 2 3 73 148 3 1 2 29 58 3 1 2 19 84 3 1 2 8 134 3 1 2 46 147 2 3 1 115 114 2 3 1 9 13 1 2 3 27 96 1 3 2 38 75 1 3 2 127 43 2 3 1 18 100 3 1 2 134 36 3 1 2 37 14 1 3 2 33 131 2 3 1 114 17 2 1 3 86 57 2 1 3 136 12 2 3 1 7 121 3 1 2 95 51 2 1 3 84 40 1 3 2 73 47 1 3 2 116 46 2 3 1 133 ...
output:
2 2 2 2 3 3 3 2 1 3 1 2 1 2 1 1 2 3 2 1 1 3 3 2 2 1 2 1 2 2 1 2 1 1 2 2 2 2 2 1 2 1 1 3 2 1 1 3 1 2 3 3 3 3 1 2 1 1 1 2 3 3 3 3 1 1 2 1 3 1 1 2 1 3 3 2 1 3 1 1 2 2 2 1 2 2 1 3 1 1 2 1 3 3 2 3 2 3 1 2 3 2 1 1 2 3 2 1 1 1 3 2 3 2 1 1 2 3 1 3 2 2 3 2 1 2 3 3 2 1 3 2 2 2 1 2 3 1 3 1 3 3 2 1 2 3 2 3 2 2 ...
result:
ok construction is correct.
Test #34:
score: 0
Accepted
time: 2ms
memory: 4324kb
input:
150 1500 10 35 119 4 6 7 8 10 3 5 9 2 1 35 5 4 1 6 7 5 8 9 3 10 2 35 18 4 1 6 9 8 2 10 7 5 3 25 90 9 10 8 1 6 4 5 3 7 2 54 132 2 3 5 4 6 9 10 8 1 7 23 122 8 3 2 6 9 10 4 7 5 1 37 108 2 9 10 7 1 6 5 4 3 8 42 45 3 1 2 4 6 9 5 8 7 10 61 54 5 10 2 1 7 6 4 8 9 3 21 10 6 2 4 3 10 1 5 8 7 9 9 68 6 3 9 5 1 ...
output:
9 8 10 10 9 10 10 9 10 8 10 10 9 5 1 9 9 10 7 10 8 8 9 10 10 10 9 10 8 5 9 7 10 6 10 7 10 10 10 6 10 9 10 9 10 5 7 3 8 1 7 10 9 9 9 9 10 10 9 8 5 7 8 10 7 10 5 9 10 10 10 7 10 9 6 5 10 5 4 10 3 10 10 10 10 8 10 10 10 8 10 8 8 9 9 9 10 5 9 10 9 9 10 8 6 2 8 6 6 9 9 7 8 6 10 9 2 10 6 10 9 6 9 9 8 9 4 ...
result:
ok construction is correct.
Test #35:
score: 0
Accepted
time: 8ms
memory: 4248kb
input:
150 1499 10 30 147 12041 480 2534 5853 460 9985 9511 2130 8477 8240 125 143 12383 3967 6251 3622 10294 1397 10212 7716 2711 6137 112 138 2728 3406 8823 707 12079 11902 11817 3859 8350 156 19 142 912 13564 8650 1043 4205 9930 2799 5040 11807 2018 4 32 10346 12401 4848 13807 13988 9904 814 4787 13290 ...
output:
460 1397 156 912 814 88 2021 4567 212 5 3132 1524 237 169 3193 2979 1039 3035 3321 649 1005 340 691 4208 241 2330 1249 436 1723 1129 540 363 2777 815 1379 4122 3495 939 1695 255 1884 101 1783 268 138 150 427 1822 975 770 3876 365 1971 4064 464 715 1046 264 132 890 939 1608 404 542 34 2742 194 1749 1...
result:
ok construction is correct.
Test #36:
score: 0
Accepted
time: 2ms
memory: 4148kb
input:
150 1498 10 13 93 4 3 7 9 11 10 5 1 6 8 135 4 11 6 5 1 10 3 2 8 4 9 75 91 3 9 2 8 5 4 1 6 10 11 137 110 10 9 6 2 1 11 3 4 7 8 77 76 5 6 11 3 8 4 9 1 10 7 69 51 2 9 1 4 10 8 5 3 7 11 18 27 10 6 3 11 5 4 1 2 8 7 122 101 11 3 4 2 6 10 8 9 5 1 56 2 7 9 1 10 4 3 11 8 5 2 1 16 2 5 10 8 11 1 9 6 3 4 18 54 ...
output:
7 8 2 3 8 9 8 8 9 9 6 9 3 4 7 9 7 3 9 8 6 6 4 11 8 10 11 10 6 10 8 4 8 7 7 8 5 10 10 1 5 6 7 6 10 10 9 8 10 1 3 7 9 10 9 9 6 10 7 7 8 9 6 4 8 9 3 9 7 10 6 6 2 6 6 9 7 9 10 9 6 6 2 8 8 6 6 8 8 9 7 1 1 10 10 10 10 10 6 1 10 9 9 9 7 10 8 3 4 6 10 8 8 7 6 7 2 10 7 4 9 1 8 9 8 3 10 5 6 3 6 6 8 10 2 6 11 ...
result:
ok construction is correct.
Test #37:
score: 0
Accepted
time: 2ms
memory: 4072kb
input:
150 1499 10 17 130 7 2 13 11 4 1 3 6 15 10 55 73 2 7 11 13 8 10 6 4 1 9 72 105 4 3 1 2 14 11 12 9 6 10 100 16 6 8 1 4 12 3 10 14 13 11 91 69 7 13 12 5 14 1 11 10 15 2 113 109 7 14 15 10 4 2 11 12 8 5 73 74 1 5 14 6 10 3 2 13 8 9 4 13 10 14 12 2 6 11 15 8 1 5 87 96 1 15 4 10 3 6 12 8 2 11 25 7 1 4 14...
output:
10 2 11 1 1 5 8 8 3 7 7 5 8 7 8 9 7 3 4 10 7 1 7 6 8 6 10 5 6 5 7 11 6 12 1 1 3 9 2 6 2 7 8 8 1 9 7 2 8 6 7 2 11 15 10 9 2 12 7 4 6 12 7 9 9 9 5 4 7 9 2 12 10 3 5 8 10 9 3 9 7 6 2 4 6 10 8 3 8 6 8 10 9 9 10 10 7 6 7 12 9 6 1 4 5 6 7 4 2 3 8 8 13 6 6 8 5 7 11 7 7 8 6 4 11 7 5 9 8 3 10 5 9 10 8 1 4 8 ...
result:
ok construction is correct.
Test #38:
score: 0
Accepted
time: 2ms
memory: 4336kb
input:
150 1400 10 101 73 1 7 5 3 10 6 2 8 4 9 100 14 6 4 8 5 9 2 10 7 1 3 89 103 3 2 5 7 1 9 4 8 6 10 31 63 5 10 6 7 9 4 2 8 1 3 81 145 6 7 5 2 9 4 10 8 1 3 103 95 4 8 3 5 2 9 10 1 7 6 14 89 1 9 2 4 10 8 5 3 6 7 90 111 7 10 8 5 4 6 3 1 9 2 82 11 10 7 1 3 9 2 8 6 5 4 5 119 6 9 7 4 10 5 8 1 3 2 147 74 9 2 6...
output:
8 6 7 7 8 7 10 7 8 10 7 8 8 8 2 7 8 9 7 9 10 9 9 6 6 8 9 5 9 6 8 7 4 6 9 3 7 9 10 6 8 10 10 7 9 7 2 10 9 8 9 7 9 10 9 7 4 8 8 10 8 8 8 7 8 5 4 7 2 10 8 6 4 6 3 9 9 7 3 7 1 7 10 9 9 2 8 8 5 7 7 9 6 5 8 8 9 10 7 4 8 10 7 6 5 8 4 2 6 6 7 3 7 7 8 8 8 9 3 7 7 8 6 2 5 7 6 8 7 8 10 10 7 8 7 6 8 3 5 6 8 8 5...
result:
ok construction is correct.
Test #39:
score: 0
Accepted
time: 6ms
memory: 4536kb
input:
150 3000 20 130 71 11 13 17 10 15 2 4 18 3 5 1 7 14 8 9 12 6 20 19 16 93 110 17 11 20 2 1 19 7 9 14 16 4 5 12 10 15 18 8 13 3 6 3 80 1 12 8 3 19 17 6 5 2 15 14 16 11 20 7 18 10 9 4 13 118 56 14 1 16 13 11 20 3 17 18 5 9 10 19 8 7 12 2 4 6 15 87 14 4 19 8 1 7 13 15 18 11 2 14 16 9 20 3 12 6 5 17 10 1...
output:
12 20 20 12 20 20 20 20 16 20 18 18 20 12 17 19 19 15 16 19 20 20 19 18 19 20 20 20 20 18 18 20 20 20 20 13 18 20 20 18 20 20 20 17 19 17 16 18 20 19 19 17 19 20 20 18 18 20 15 18 19 19 20 19 16 20 20 4 17 20 18 2 19 20 20 19 17 6 20 5 20 19 20 17 15 20 18 18 18 17 12 20 12 20 20 11 15 16 20 16 19 1...
result:
ok construction is correct.
Test #40:
score: 0
Accepted
time: 30ms
memory: 6500kb
input:
150 2997 20 137 131 5762 9111 38967 15773 52237 2826 21697 38030 50735 19494 3273 2767 35083 37295 10180 21810 12236 12874 15065 37851 29 78 50409 52886 11932 43949 7925 40147 2771 49165 639 12786 39123 36098 18441 22546 59053 36310 28727 8858 36938 4917 31 45 14688 22548 41715 42035 1729 54934 3718...
output:
2767 639 1729 1938 907 1845 1704 646 3458 3339 1654 3757 3315 4354 2477 2172 1885 420 6361 2769 2497 6432 6448 284 6098 6151 2444 10474 2186 705 4538 3556 1141 3099 1573 1469 8171 952 2435 6205 6432 629 7305 2348 5490 4726 1721 2058 2595 4916 3513 688 5627 2128 3483 1798 2564 9228 1245 1669 11597 33...
result:
ok construction is correct.
Test #41:
score: 0
Accepted
time: 3ms
memory: 4456kb
input:
150 2998 20 57 43 1 2 17 16 7 9 11 15 6 3 12 20 10 21 5 14 4 13 18 19 70 32 13 15 17 8 19 3 6 5 1 18 16 7 21 4 9 14 12 10 20 11 119 97 2 13 19 4 21 11 8 15 9 16 1 3 10 14 12 17 7 5 6 18 31 74 12 13 20 19 18 11 6 4 10 1 9 8 3 7 2 17 5 14 21 16 40 144 15 3 6 17 9 5 13 21 18 12 14 11 20 7 10 1 19 16 2 ...
output:
18 17 8 18 18 20 19 19 20 18 20 20 17 19 18 18 16 20 14 17 16 20 18 21 15 19 4 19 11 14 18 20 19 19 17 20 20 5 19 20 18 16 20 19 17 17 18 10 20 12 19 18 19 20 20 18 20 16 18 9 15 18 17 9 9 20 16 20 19 19 17 20 6 17 18 13 20 19 18 16 19 18 20 20 16 15 20 19 13 19 15 18 19 17 12 18 18 16 18 19 19 19 1...
result:
ok construction is correct.
Test #42:
score: 0
Accepted
time: 6ms
memory: 4408kb
input:
150 2997 20 63 21 8 6 4 1 19 14 10 16 18 24 2 21 5 3 15 17 7 9 23 12 40 101 12 24 13 18 10 21 22 19 16 15 14 1 23 8 4 2 25 5 7 20 32 150 18 24 16 13 3 22 23 9 20 8 12 14 15 1 25 5 2 6 11 21 122 137 25 7 11 8 5 24 10 22 18 15 9 20 4 16 13 12 17 3 19 6 72 105 12 13 4 21 10 17 24 20 25 9 18 8 14 5 16 1...
output:
16 19 13 7 18 22 12 19 13 17 16 18 11 14 9 16 15 21 19 13 20 10 19 15 15 5 17 19 14 16 18 19 20 6 18 10 18 16 16 20 18 21 14 11 15 19 18 18 7 14 13 20 15 20 21 16 23 14 14 19 17 14 8 11 17 14 17 15 15 20 18 12 20 14 17 15 18 15 19 15 8 19 19 13 15 12 18 7 7 18 19 6 13 9 16 20 16 11 11 15 10 13 21 17...
result:
ok construction is correct.
Test #43:
score: 0
Accepted
time: 3ms
memory: 4404kb
input:
150 2900 20 84 108 9 13 4 12 20 6 7 2 11 15 14 1 17 8 16 18 19 3 10 5 24 23 6 13 2 8 20 17 1 4 3 19 12 7 11 16 14 9 5 10 15 18 141 53 11 8 2 13 19 1 12 9 18 4 6 3 14 16 17 15 20 5 10 7 37 109 8 7 2 18 4 17 12 6 16 20 19 13 11 1 10 14 5 3 15 9 88 3 4 20 3 1 15 2 18 7 11 17 9 19 10 12 13 14 6 16 5 8 3...
output:
19 19 15 19 20 19 19 14 19 20 18 18 18 20 13 11 20 19 16 20 20 18 18 17 17 9 15 13 20 11 17 16 18 18 14 17 17 19 15 19 19 13 20 20 17 20 19 8 18 12 15 19 17 20 17 10 18 18 19 19 19 18 18 15 20 18 18 17 19 18 18 20 12 20 20 12 19 18 18 15 14 19 17 17 17 19 19 16 19 18 17 17 17 18 5 12 20 19 19 17 13 ...
result:
ok construction is correct.
Test #44:
score: 0
Accepted
time: 28ms
memory: 7068kb
input:
150 7494 50 57 77 43 20 29 31 16 40 17 1 37 48 24 33 15 22 23 38 41 7 3 42 11 12 45 5 27 36 8 25 26 34 2 10 19 21 46 6 50 39 44 13 32 4 14 35 47 18 49 9 30 28 7 123 33 10 24 45 26 3 40 11 6 27 29 35 32 17 20 13 8 31 9 37 38 7 1 5 16 43 12 4 28 30 14 36 25 48 49 2 34 41 47 39 21 42 44 19 50 46 18 22 ...
output:
50 50 49 16 50 50 50 41 43 17 49 48 41 50 41 24 14 45 50 44 49 30 49 48 49 48 46 49 48 49 48 49 47 49 49 44 37 50 50 50 40 50 50 48 50 47 49 50 44 48 47 50 48 50 50 50 48 50 30 31 33 48 41 47 48 50 48 50 48 48 47 50 49 48 50 50 35 49 50 48 49 50 50 32 46 47 45 50 50 37 49 50 50 50 48 48 46 48 50 49 ...
result:
ok construction is correct.
Test #45:
score: 0
Accepted
time: 28ms
memory: 7584kb
input:
150 7483 50 30 40 19 50 18 29 7 53 30 22 1 31 25 20 43 23 55 16 40 42 9 15 3 33 10 35 41 51 44 32 46 21 49 39 34 48 13 28 45 36 24 8 52 47 37 12 4 26 27 11 38 2 7 59 46 18 6 9 52 19 35 21 24 28 39 54 14 16 11 20 41 23 17 7 5 31 8 29 51 25 33 53 4 22 15 37 48 44 32 2 30 47 13 49 10 3 43 34 42 45 12 1...
output:
48 47 49 49 10 48 39 49 38 39 34 47 49 45 49 49 47 46 40 49 37 49 5 48 49 47 46 44 48 25 35 49 48 48 47 49 45 49 49 50 47 39 51 47 46 49 41 39 49 44 46 51 50 47 45 50 44 49 50 50 46 43 46 50 46 37 36 48 45 49 48 50 48 47 49 43 45 50 49 49 44 51 46 44 46 50 45 17 47 27 47 50 49 47 46 43 47 50 47 46 4...
result:
ok construction is correct.
Test #46:
score: 0
Accepted
time: 103ms
memory: 17248kb
input:
150 14979 100 51 51 23 8 1 82 39 77 42 18 99 74 78 60 49 86 100 63 59 12 52 87 14 83 48 33 5 50 67 34 94 75 28 38 24 70 51 97 7 35 30 55 80 66 10 37 11 41 25 89 68 17 95 56 84 92 90 85 6 81 96 62 57 27 2 20 69 15 4 53 36 16 40 71 45 22 93 88 46 79 58 3 91 64 32 9 21 73 76 29 26 54 65 44 13 72 19 47 ...
output:
99 99 99 99 93 99 86 99 99 99 98 93 99 99 99 99 84 99 95 96 98 99 98 99 99 99 92 99 95 87 98 99 99 99 99 99 99 98 95 47 66 72 97 96 97 99 98 99 47 97 97 99 98 98 97 99 93 99 98 99 98 96 98 98 80 95 97 94 91 99 79 84 98 95 99 98 97 100 99 99 97 99 98 99 95 97 96 99 98 97 99 94 96 98 98 99 97 97 96 98...
result:
ok construction is correct.
Test #47:
score: 0
Accepted
time: 98ms
memory: 17652kb
input:
150 14976 100 49 146 50 24 101 73 47 94 6 79 38 8 75 64 36 89 15 29 97 23 56 98 74 17 44 3 7 58 65 49 14 105 21 52 95 12 59 28 10 27 2 69 32 11 91 80 26 87 82 40 48 4 35 100 53 88 5 41 55 72 66 42 22 9 63 85 76 68 77 84 70 45 30 39 57 46 51 60 86 93 61 25 13 19 18 103 96 62 20 99 83 92 33 67 90 54 7...
output:
100 101 98 99 99 98 100 93 90 87 99 97 87 99 90 100 100 96 100 97 99 88 97 98 99 97 97 100 98 99 94 97 97 97 100 100 93 98 50 100 99 98 98 97 92 100 93 96 97 99 100 100 91 99 94 75 98 96 99 97 97 98 89 98 78 99 94 97 41 99 98 94 90 98 91 93 98 89 99 99 98 94 94 98 97 99 98 97 100 98 97 97 96 100 70 ...
result:
ok construction is correct.
Test #48:
score: 0
Accepted
time: 204ms
memory: 32908kb
input:
150 20969 140 12 46 41 108 67 140 21 20 11 126 62 100 117 5 76 64 49 60 3 58 55 19 133 85 98 10 18 63 26 122 39 96 115 69 34 53 24 110 45 112 61 120 71 82 129 92 131 16 105 43 138 74 31 95 130 102 17 81 14 70 77 12 32 38 23 124 79 40 86 90 101 123 59 78 94 2 30 118 13 33 65 121 56 116 80 127 44 128 ...
output:
139 138 139 138 128 139 139 139 139 139 139 68 137 138 139 139 139 139 126 139 137 139 123 138 134 139 139 132 119 127 139 138 139 139 139 139 139 138 139 139 137 132 138 139 140 128 139 139 134 121 136 139 140 137 136 138 139 137 139 138 124 120 139 139 138 139 136 138 139 139 139 138 137 139 139 1...
result:
ok construction is correct.
Test #49:
score: 0
Accepted
time: 202ms
memory: 32900kb
input:
150 20965 140 45 102 99 102 76 9 81 45 94 24 123 52 60 114 75 80 38 51 33 47 49 134 66 39 107 28 141 21 89 3 18 138 12 57 26 77 96 58 43 88 119 10 59 109 98 35 42 11 74 73 140 126 86 56 41 44 90 108 93 46 54 34 83 144 65 27 15 78 14 61 72 4 139 13 48 142 71 101 37 122 25 115 145 5 85 22 16 23 36 136...
output:
138 137 135 137 139 140 94 100 133 139 139 140 134 140 138 138 134 140 126 138 138 137 135 79 139 137 139 132 127 137 99 118 139 139 137 136 124 140 140 137 138 140 139 139 137 139 138 135 140 140 138 138 138 137 137 136 135 140 139 138 131 138 136 136 132 138 140 140 125 139 135 136 136 138 111 138...
result:
ok construction is correct.
Test #50:
score: 0
Accepted
time: 213ms
memory: 36060kb
input:
150 22317 149 103 74 87 10 60 134 108 54 24 40 13 133 128 31 77 11 135 148 66 137 94 33 105 107 39 91 123 30 89 101 67 65 55 72 145 21 61 76 113 139 121 46 122 22 84 82 19 12 131 125 36 51 126 112 69 129 85 95 38 28 7 48 14 149 70 63 130 111 50 41 117 109 71 83 35 64 44 23 49 78 144 90 124 27 98 114...
output:
148 113 147 135 149 141 148 135 141 146 144 145 148 148 148 148 148 148 148 148 139 144 148 148 147 132 146 148 149 148 139 148 147 137 149 148 148 148 147 148 144 148 145 147 144 146 125 147 147 148 136 135 148 148 145 148 145 147 147 147 148 146 147 139 148 142 147 148 148 148 148 130 147 145 148 ...
result:
ok construction is correct.
Test #51:
score: 0
Accepted
time: 217ms
memory: 36032kb
input:
150 22316 149 66 109 81 34 109 53 56 134 62 125 84 57 89 50 100 136 14 124 146 86 78 16 118 55 54 128 44 147 10 142 129 63 107 45 148 19 123 116 113 59 17 95 105 24 5 150 43 141 1 74 85 26 93 112 143 108 30 88 65 83 104 9 97 115 90 114 145 38 13 35 126 11 29 2 92 91 52 121 82 60 151 28 140 22 72 117...
output:
147 148 146 147 146 150 147 147 140 147 135 148 135 136 148 147 146 134 147 138 148 148 147 146 142 147 149 148 149 146 138 144 148 146 134 146 145 148 149 149 149 143 148 148 116 143 147 148 147 149 148 147 145 149 147 132 143 146 148 149 143 147 148 145 147 146 147 147 119 146 148 142 146 145 122 ...
result:
ok construction is correct.
Extra Test:
score: 0
Extra Test Passed