QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#300148 | #5529. Most Annoying Constructive Problem | hos_lyric | AC ✓ | 10ms | 3824kb | C++14 | 8.0kb | 2024-01-07 19:12:21 | 2024-01-07 19:12:21 |
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")
int eval(const vector<int> &ps) {
const int n = ps.size();
vector<vector<int>> f(n, vector<int>(n, 0));
for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) if (ps[i] > ps[j]) ++f[i][j];
for (int i = n - 1; --i >= 0; ) for (int j = 0; j < n; ++j) f[i][j] += f[i + 1][j];
for (int i = 0; i < n; ++i) for (int j = 1; j < n; ++j) f[i][j] += f[i][j - 1];
int k = 0;
for (int i = 0; i < n; ++i) for (int j = i; j < n; ++j) if (f[i][j] & 1) ++k;
return k;
}
vector<int> getBest(int n) {
assert(n >= 4);
if (n % 2 != 0) {
auto ps = getBest(n - 1);
ps.push_back(n - 1);
return ps;
} else {
vector<int> ps(n);
for (int i = 0; i < n; ++i) ps[i] = (i&1) ? (i - 2) : (i + 2);
ps[1] = 0;
ps[n - 2] = n - 1;
return ps;
}
}
vector<int> getCest(int n) {
assert(n >= 6);
assert(n % 2 == 0);
vector<int> ps(n);
for (int i = 0; i < n; ++i) ps[i] = (i&1) ? (i + 2) : (i - 2);
ps[0] = 0;
ps[2] = 1;
ps[n - 3] = n - 2;
ps[n - 1] = n - 1;
return ps;
}
vector<int> move(vector<int> ps, int i0, int a0) {
const int n = ps.size();
for (int i = 0; i < n; ++i) if (i0 != i && ps[i] > ps[i0]) --ps[i];
for (int i = 0; i < n; ++i) if (i0 != i && ps[i] >= a0) ++ps[i];
ps[i0] = a0;
return ps;
}
int calc(int n) {
if (n == 1) return 0;
if (n == 2) return 1;
if (n == 3) return 3;
assert(n >= 4);
return n*(n-1)/2 - (n - 1) / 2;
}
vector<int> solve(int N, int K) {
if (!(0 <= K && K <= calc(N))) return {};
// zero
if (K == 0) {
vector<int> ps(N);
for (int i = 0; i < N; ++i) ps[i] = i;
return ps;
}
// easy
if (1 <= K && K <= N - 2) {
vector<int> ps(N);
for (int i = 0; i < N; ++i) ps[i] = i;
ps[K - 1] = K + 1;
ps[K ] = K - 1;
ps[K + 1] = K ;
return ps;
}
// inductive
if (N - 2 >= 1 && (N - 1) <= K && K <= calc(N - 2) + (N - 1)) {
int n = N, k = K;
do {
k -= (n - 1);
n -= 2;
} while (n - 2 >= 1 && (n - 1) <= k && k <= calc(n - 2) + (n - 1));
auto ps = solve(n, k);
for (; n < N; ) {
n += 2;
ps.push_back(n - 1);
ps.push_back(n - 2);
}
return ps;
}
if (N >= 4) {
const int d = calc(N) - K;
const auto best = getBest(N);
// best
if (d == 0) return best;
// cest or move
if (d == 1) {
if (N >= 6 && N % 2 == 0) return getCest(N);
if (N >= 7 && N % 2 != 0) return move(best, N - 1, N - 5);
}
// move
if (d == 2) return move(best, 0, 0);
int now = 2, a = 4;
for (; ; ) {
++now;
// cerr<<"N = "<<N<<", now = "<<now<<", a = "<<a<<endl;
if (d == now) return move(best, 0, a);
a = (a % 2 != 0) ? (a - 2) : (a == N - 3) ? (a - 1) : (a == N - 4) ? (a + 1) : (a + 2);
}
}
// special
if (N == 2 && K == 1) return {1, 0};
if (N == 3 && K == 3) return {2, 1, 0};
cerr<<"HELP "<<N<<" "<<K<<endl;
assert(false);
}
void expr() {
constexpr int LIM_N = 11;
vector<vector<vector<vector<int>>>> brt(LIM_N + 1);
for (int n = 1; n <= LIM_N; ++n) {
string status(n*(n-1)/2 + 1, 'x');
brt[n].assign(n*(n-1)/2 + 1, {});
{
vector<int> ps(n);
for (int i = 0; i < n; ++i) ps[i] = i;
do {
const int k = eval(ps);
status[k] = 'o';
brt[n][k].push_back(ps);
} while (next_permutation(ps.begin(), ps.end()));
}
for (int k = 0; k <= n*(n-1)/2; ++k) if (brt[n][k].size()) {
cout << n << " " << k << endl;
cout << brt[n][k][0] << endl;
cout << brt[n][k].back() << endl;
cout << endl;
}
// zero
status[0] = '0';
// easy
for (int i0 = 0; i0 + 3 <= n; ++i0) {
vector<int> ps(n);
for (int i = 0; i < n; ++i) ps[i] = i;
ps[i0 + 0] = i0 + 2;
ps[i0 + 1] = i0 + 0;
ps[i0 + 2] = i0 + 1;
const int k = eval(ps);
// cerr<<n<<" "<<i0<<" "<<ps<<" "<<k<<endl;
if (status[k] == 'o') status[k] = 'E';
}
// inductive
if (n - 2 >= 1) {
for (int k2 = 0; k2 <= (n-2)*(n-3)/2; ++k2) if (brt[n - 2][k2].size()) {
auto ps = brt[n - 2][k2][0];
ps.push_back(n - 1);
ps.push_back(n - 2);
const int k = eval(ps);
assert(k2 + (n - 1) == k);
if (status[k] == 'o') status[k] = 'I';
}
}
// best
if (n >= 4) {
const auto ps = getBest(n);
const int k = eval(ps);
assert(k == calc(n));
cerr<<"best "<<n<<" "<<ps<<" "<<k<<endl;
if (status[k] == 'o') status[k] = 'B';
}
// cest
if (n >= 6 && n % 2 == 0) {
const auto ps = getCest(n);
const int k = eval(ps);
// cerr<<"cest "<<n<<" "<<ps<<" "<<k<<endl;
if (status[k] == 'o') status[k] = 'C';
}
// move
if (n >= 4) {
const auto best = getBest(n);
for (const int i0 : {0, n - 1}) for (int a0 = 0; a0 < n; ++a0) {
const auto ps = move(best, i0, a0);
const int k = eval(ps);
cerr<<"move "<<n<<" "<<i0<<" "<<a0<<" "<<ps<<" "<<k<<endl;
if (status[k] == 'o') status[k] = 'M';
}
}
cerr << (n/10) << (n%10) << ": " << status;
if (n - 2 >= 1) cerr << " " << calc(n) << " " << (calc(n - 2) + (n - 1));
cerr << endl;
for (int k = 0; k <= n*(n-1)/2; ++k) if (status[k] == 'o') {
cerr << "special " << n << " " << k << endl;
for (const auto &ps : brt[n][k]) {
cerr << ps << endl;
}
}
for (int k = 0; k <= n*(n-1)/2; ++k) {
const auto slv = solve(n, k);
if (brt[n][k].size()) {
assert(slv.size());
auto it = lower_bound(brt[n][k].begin(), brt[n][k].end(), slv);
if (it != brt[n][k].end() && *it == slv) {
//
} else {
cerr << "FAIL " << n << " " << k << ": " << slv << endl;
assert(false);
}
} else {
assert(!slv.size());
}
}
cerr << "PASSED n = " << n << endl;
}
for (int n = LIM_N + 1; n <= 20; ++n) {
for (int k = 0; k <= n*(n-1)/2; ++k) {
const auto slv = solve(n, k);
if (k <= calc(n)) {
assert(slv.size());
assert(k == eval(slv));
} else {
assert(!slv.size());
}
}
cerr << "PASSED n = " << n << endl;
}
}
int main() {
// expr();
for (int numCases; ~scanf("%d", &numCases); ) { for (int caseId = 1; caseId <= numCases; ++caseId) {
int N, K;
scanf("%d%d", &N, &K);
const auto ans = solve(N, K);
if (ans.size()) {
puts("YES");
for (int i = 0; i < N; ++i) {
if (i) printf(" ");
printf("%d", ans[i] + 1);
}
puts("");
} else {
puts("NO");
}
}
#ifndef LOCAL
break;
#endif
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3704kb
input:
4 1 0 3 3 4 1 6 15
output:
YES 1 YES 3 2 1 YES 3 1 2 4 NO
result:
ok Correct (4 test cases)
Test #2:
score: 0
Accepted
time: 10ms
memory: 3820kb
input:
5951 27 255 28 371 31 320 33 201 32 199 31 108 15 78 27 32 24 268 20 4 14 82 29 202 33 85 26 104 31 380 27 330 20 140 29 192 21 63 17 89 20 41 32 444 20 76 27 114 33 330 26 249 33 301 24 87 25 72 14 49 25 281 21 58 15 48 16 19 14 0 22 175 11 7 30 43 31 259 22 112 12 30 30 111 33 268 30 287 19 150 15...
output:
YES 6 1 4 2 7 3 9 5 11 8 13 10 15 12 17 14 19 16 20 18 21 23 22 25 24 27 26 NO YES 19 1 4 2 6 3 8 5 10 7 12 9 14 11 16 13 18 15 20 17 21 23 22 25 24 27 26 29 28 31 30 YES 3 1 2 4 5 6 7 8 9 10 11 12 13 14 15 16 17 19 18 21 20 23 22 25 24 27 26 29 28 31 30 33 32 YES 1 2 3 4 5 6 9 7 8 10 11 12 13 14 15...
result:
ok Correct (5951 test cases)
Test #3:
score: 0
Accepted
time: 8ms
memory: 3712kb
input:
3201 37 408 37 275 34 107 35 521 36 552 37 582 35 81 36 53 34 16 33 40 34 70 33 305 36 367 35 55 35 15 35 416 33 92 36 590 33 206 35 241 34 404 36 154 35 582 33 359 36 25 37 412 38 162 36 579 34 194 35 92 36 429 36 458 37 662 35 71 34 78 35 90 36 304 33 448 36 98 36 605 34 31 34 421 35 509 37 90 36 ...
output:
YES 11 1 4 2 6 3 8 5 10 7 13 9 15 12 17 14 18 16 19 21 20 23 22 25 24 27 26 29 28 31 30 33 32 35 34 37 36 YES 1 2 3 4 7 5 6 8 9 10 11 12 13 14 15 16 17 19 18 21 20 23 22 25 24 27 26 29 28 31 30 33 32 35 34 37 36 YES 1 2 3 4 5 6 7 8 9 10 11 12 13 16 14 15 17 18 19 20 21 22 23 24 25 26 27 28 30 29 32 ...
result:
ok Correct (3201 test cases)
Test #4:
score: 0
Accepted
time: 3ms
memory: 3712kb
input:
2587 39 606 40 291 40 10 40 382 38 71 40 558 38 179 41 178 40 479 39 596 40 356 41 303 39 415 38 528 39 204 39 432 38 484 38 365 38 690 38 431 40 733 38 364 40 746 40 409 40 240 41 342 39 278 38 79 39 573 39 118 38 653 40 600 40 252 38 628 40 611 41 242 40 650 39 195 38 114 39 551 39 620 40 15 38 51...
output:
YES 27 1 4 2 6 3 8 5 10 7 12 9 14 11 16 13 18 15 20 17 22 19 24 21 26 23 29 25 31 28 32 30 33 35 34 37 36 39 38 YES 1 2 3 4 5 6 7 8 9 10 11 14 12 13 15 16 17 18 19 20 21 22 24 23 26 25 28 27 30 29 32 31 34 33 36 35 38 37 40 39 YES 1 2 3 4 5 6 7 8 9 12 10 11 13 14 15 16 17 18 19 20 21 22 23 24 25 26 ...
result:
ok Correct (2587 test cases)
Test #5:
score: 0
Accepted
time: 6ms
memory: 3704kb
input:
2277 41 527 41 310 41 697 41 108 42 610 41 320 42 390 43 482 43 266 42 2 42 599 43 95 43 204 41 392 42 29 41 57 43 201 42 465 43 166 43 169 42 471 41 539 41 358 41 100 43 60 42 475 42 604 41 451 41 246 42 61 42 113 42 36 43 437 41 532 43 582 43 573 41 312 42 638 42 590 42 632 42 621 43 464 41 654 43...
output:
YES 5 1 4 2 7 3 9 6 11 8 13 10 15 12 17 14 19 16 21 18 22 20 23 25 24 27 26 29 28 31 30 33 32 35 34 37 36 39 38 41 40 YES 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 23 22 25 24 27 26 29 28 31 30 33 32 35 34 37 36 39 38 41 40 YES 14 1 4 2 6 3 8 5 10 7 12 9 15 11 17 13 19 16 21 18 23 20 25 ...
result:
ok Correct (2277 test cases)
Test #6:
score: 0
Accepted
time: 3ms
memory: 3708kb
input:
2095 43 903 43 836 43 288 43 362 44 461 44 748 43 360 45 160 45 111 44 696 43 518 43 441 43 636 43 853 44 594 43 23 43 540 44 167 44 735 43 317 43 127 44 795 43 347 43 445 44 388 43 880 44 177 43 744 43 131 44 208 43 521 43 342 45 128 44 908 43 843 45 36 43 404 43 311 43 185 44 727 44 599 43 375 43 ...
output:
NO YES 11 1 4 2 6 3 8 5 10 7 13 9 15 12 17 14 19 16 21 18 23 20 25 22 27 24 29 26 31 28 33 30 35 32 37 34 39 36 40 38 41 43 42 YES 1 2 3 4 5 6 7 10 8 9 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 29 28 31 30 33 32 35 34 37 36 39 38 41 40 43 42 YES 1 2 3 4 5 6 7 8 9 12 10 11 13 14 15 16 17 18 ...
result:
ok Correct (2095 test cases)
Test #7:
score: 0
Accepted
time: 6ms
memory: 3720kb
input:
1932 45 489 46 403 45 883 46 531 45 906 45 54 45 320 45 410 45 425 45 719 45 342 46 628 46 508 45 950 45 825 46 309 46 687 46 164 46 284 46 634 45 87 45 836 46 719 46 313 45 687 45 602 45 773 46 629 46 301 46 219 45 59 46 670 46 58 45 538 46 33 45 229 45 919 45 805 46 107 45 971 46 335 45 555 45 552...
output:
YES 1 2 5 3 4 6 7 8 9 11 10 13 12 15 14 17 16 19 18 21 20 23 22 25 24 27 26 29 28 31 30 33 32 35 34 37 36 39 38 41 40 43 42 45 44 YES 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 20 18 19 21 22 23 24 26 25 28 27 30 29 32 31 34 33 36 35 38 37 40 39 42 41 44 43 46 45 YES 5 1 4 2 7 3 9 6 11 8 13 10 15 12 ...
result:
ok Correct (1932 test cases)
Test #8:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
1585 50 173 50 325 51 176 50 136 51 211 50 766 51 203 51 107 51 145 50 990 50 1054 50 542 50 135 51 234 51 302 50 346 50 1051 50 733 51 27 50 559 50 967 50 38 50 861 50 832 50 83 50 551 51 33 51 332 50 977 50 466 51 146 50 912 51 312 50 256 50 891 50 1076 51 319 50 710 50 269 50 689 51 143 50 259 50...
output:
YES 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 34 32 33 35 36 37 38 39 40 41 42 43 44 46 45 48 47 50 49 YES 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 26 24 25 27 28 29 30 31 32 33 34 35 36 38 37 40 39 42 41 44 43 46 45 48 47 50 49 YES 1 2 3 ...
result:
ok Correct (1585 test cases)
Test #9:
score: 0
Accepted
time: 5ms
memory: 3712kb
input:
1422 53 964 53 573 53 593 53 923 53 901 53 1244 53 29 54 2 53 544 53 89 53 229 53 304 53 1035 53 1002 53 184 53 951 53 1123 53 1167 53 32 53 1342 53 1037 53 1280 53 943 53 850 53 309 53 925 53 587 53 238 53 714 53 872 53 52 54 24 53 233 53 908 53 672 53 1286 53 910 54 21 53 407 53 106 53 555 53 764 ...
output:
YES 19 1 4 2 6 3 8 5 10 7 12 9 14 11 16 13 18 15 21 17 23 20 25 22 27 24 29 26 31 28 33 30 34 32 35 37 36 39 38 41 40 43 42 45 44 47 46 49 48 51 50 53 52 YES 1 2 5 3 4 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 25 24 27 26 29 28 31 30 33 32 35 34 37 36 39 38 41 40 43 42 45 44 47 46 49 48 51 5...
result:
ok Correct (1422 test cases)
Test #10:
score: 0
Accepted
time: 3ms
memory: 3708kb
input:
400 100 221 100 321 100 334 100 1 100 17 100 166 100 312 100 186 100 343 100 39 100 206 100 288 100 134 100 127 100 159 100 307 100 105 100 160 100 213 100 319 100 337 100 264 100 181 100 115 100 267 100 308 100 171 100 192 100 140 100 309 100 189 100 20 100 350 100 130 100 376 100 246 100 165 100 3...
output:
YES 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 27 25 26 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 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 98 97 100 99 YES ...
result:
ok Correct (400 test cases)
Test #11:
score: 0
Accepted
time: 2ms
memory: 3724kb
input:
1078 53 1368 56 1539 56 1510 52 1326 51 1234 65 2063 60 1740 60 1751 53 1355 69 2337 70 2415 61 1797 52 1325 61 1796 59 1669 57 1567 70 2412 65 2030 68 2271 61 1814 69 2314 50 1219 67 2182 66 2141 51 1268 61 1806 62 1865 68 2231 69 2324 59 1703 66 2128 68 2246 64 2007 55 1463 68 2225 71 2451 71 2436...
output:
NO NO YES 5 1 4 2 7 3 9 6 11 8 13 10 15 12 17 14 19 16 21 18 23 20 25 22 27 24 29 26 31 28 33 30 35 32 37 34 39 36 41 38 43 40 45 42 47 44 49 46 51 48 53 50 55 52 56 54 NO YES 31 1 4 2 6 3 8 5 10 7 12 9 14 11 16 13 18 15 20 17 22 19 24 21 26 23 28 25 30 27 33 29 35 32 37 34 39 36 41 38 43 40 45 42 4...
result:
ok Correct (1078 test cases)
Test #12:
score: 0
Accepted
time: 2ms
memory: 3708kb
input:
683 77 2903 77 2909 73 2616 73 2626 80 3140 79 3065 79 3046 77 2895 78 2968 82 3273 82 3298 79 3058 82 3265 76 2830 81 3236 72 2518 79 3068 79 3056 76 2800 82 3270 73 2577 78 3001 80 3134 78 2994 72 2546 79 3038 76 2796 78 2991 82 3267 74 2651 79 3080 71 2477 78 2971 77 2901 79 3077 75 2723 82 3299 ...
output:
NO NO NO NO NO NO NO NO NO YES 15 1 4 2 6 3 8 5 10 7 12 9 14 11 17 13 19 16 21 18 23 20 25 22 27 24 29 26 31 28 33 30 35 32 37 34 39 36 41 38 43 40 45 42 47 44 49 46 51 48 53 50 55 52 57 54 59 56 61 58 63 60 65 62 67 64 69 66 71 68 73 70 75 72 77 74 79 76 81 78 82 80 NO NO YES 31 1 4 2 6 3 8 5 10 7 ...
result:
ok Correct (683 test cases)
Test #13:
score: 0
Accepted
time: 2ms
memory: 3712kb
input:
542 88 3815 83 3358 89 3864 86 3595 90 3962 84 3439 89 3879 90 3949 83 3394 86 3615 87 3706 87 3739 84 3427 88 3812 88 3774 86 3649 82 3289 82 3311 85 3518 85 3512 89 3873 83 3363 86 3600 88 3795 89 3862 83 3356 88 3781 90 3942 89 3878 85 3552 83 3391 82 3294 85 3535 86 3601 84 3455 85 3533 87 3700 ...
output:
NO YES 7 1 4 2 6 3 9 5 11 8 13 10 15 12 17 14 19 16 21 18 23 20 25 22 27 24 29 26 31 28 33 30 35 32 37 34 39 36 41 38 43 40 45 42 47 44 49 46 51 48 53 50 55 52 57 54 59 56 61 58 63 60 65 62 67 64 69 66 71 68 73 70 75 72 77 74 79 76 81 78 82 80 83 YES 15 1 4 2 6 3 8 5 10 7 12 9 14 11 17 13 19 16 21 1...
result:
ok Correct (542 test cases)
Test #14:
score: 0
Accepted
time: 1ms
memory: 3824kb
input:
462 90 3942 92 4165 90 3961 95 4435 90 3989 92 4166 91 4082 93 4259 95 4441 96 4554 91 4058 95 4463 93 4271 96 4521 96 4507 94 4360 96 4518 95 4433 94 4354 92 4144 95 4407 96 4500 95 4442 93 4266 92 4183 96 4514 91 4072 91 4043 91 4050 92 4122 95 4453 95 4412 91 4088 93 4233 95 4437 96 4529 94 4340 ...
output:
YES 37 1 4 2 6 3 8 5 10 7 12 9 14 11 16 13 18 15 20 17 22 19 24 21 26 23 28 25 30 27 32 29 34 31 36 33 39 35 41 38 43 40 45 42 47 44 49 46 51 48 53 50 55 52 57 54 59 56 61 58 63 60 65 62 67 64 69 66 71 68 73 70 75 72 77 74 79 76 81 78 83 80 85 82 87 84 89 86 90 88 NO YES 3 1 5 2 7 4 9 6 11 8 13 10 1...
result:
ok Correct (462 test cases)
Test #15:
score: 0
Accepted
time: 1ms
memory: 3704kb
input:
412 96 4543 100 4908 100 4906 99 4838 98 4693 96 4507 101 5036 100 4886 97 4622 97 4640 97 4590 98 4732 97 4648 97 4607 99 4846 99 4800 100 4919 100 4887 100 4940 99 4816 97 4631 100 4892 98 4741 96 4547 99 4786 99 4849 97 4621 97 4609 98 4687 100 4903 98 4748 99 4830 96 4553 96 4504 97 4629 97 4642...
output:
NO NO NO NO YES 23 1 4 2 6 3 8 5 10 7 12 9 14 11 16 13 18 15 20 17 22 19 25 21 27 24 29 26 31 28 33 30 35 32 37 34 39 36 41 38 43 40 45 42 47 44 49 46 51 48 53 50 55 52 57 54 59 56 61 58 63 60 65 62 67 64 69 66 71 68 73 70 75 72 77 74 79 76 81 78 83 80 85 82 87 84 89 86 91 88 93 90 95 92 97 94 98 96...
result:
ok Correct (412 test cases)
Test #16:
score: 0
Accepted
time: 2ms
memory: 3712kb
input:
375 104 5315 102 5092 101 5042 101 4989 104 5328 104 5300 103 5248 106 5503 102 5119 102 5134 102 5141 103 5196 103 5247 104 5302 102 5086 105 5392 101 4996 104 5335 104 5327 101 4982 104 5348 101 5041 106 5504 105 5412 105 5395 102 5136 103 5217 105 5435 103 5188 103 5229 102 5091 104 5333 102 5114...
output:
NO YES 17 1 4 2 6 3 8 5 10 7 12 9 14 11 16 13 19 15 21 18 23 20 25 22 27 24 29 26 31 28 33 30 35 32 37 34 39 36 41 38 43 40 45 42 47 44 49 46 51 48 53 50 55 52 57 54 59 56 61 58 63 60 65 62 67 64 69 66 71 68 73 70 75 72 77 74 79 76 81 78 83 80 85 82 87 84 89 86 91 88 93 90 95 92 97 94 99 96 101 98 1...
result:
ok Correct (375 test cases)
Test #17:
score: 0
Accepted
time: 9ms
memory: 3708kb
input:
9156 15 93 28 362 30 431 22 176 30 431 17 121 12 66 20 173 23 247 10 40 14 80 27 341 21 207 21 25 25 292 23 240 10 23 20 184 17 14 12 34 12 58 26 324 23 139 11 53 15 89 26 321 28 357 24 93 11 51 23 246 13 68 25 282 28 367 23 237 17 120 24 258 30 237 19 170 20 181 27 337 23 245 17 123 23 249 12 34 23...
output:
YES 9 1 4 2 6 3 8 5 11 7 13 10 14 12 15 YES 5 1 4 2 7 3 9 6 11 8 13 10 15 12 17 14 19 16 21 18 23 20 25 22 27 24 28 26 NO YES 16 1 4 2 6 3 8 5 10 7 12 9 14 11 17 13 18 15 20 19 22 21 NO YES 13 1 4 2 6 3 8 5 10 7 12 9 15 11 16 14 17 NO YES 15 1 4 2 6 3 8 5 10 7 12 9 14 11 17 13 19 16 20 18 NO YES 1 4...
result:
ok Correct (9156 test cases)
Test #18:
score: 0
Accepted
time: 4ms
memory: 3724kb
input:
1560 58 1629 41 812 47 1052 58 1617 59 718 56 1538 59 1678 45 961 47 1061 47 1048 45 968 46 792 52 993 44 793 60 1760 53 1352 41 152 53 1349 46 9 47 1050 52 897 48 74 49 1154 55 490 60 910 44 929 46 1010 57 1594 56 1503 43 896 41 807 46 1011 42 339 54 898 51 1259 51 1250 53 1366 49 1162 59 1692 57 1...
output:
NO NO YES 11 1 4 2 6 3 8 5 10 7 13 9 15 12 17 14 19 16 21 18 23 20 25 22 27 24 29 26 31 28 33 30 35 32 37 34 39 36 41 38 43 40 45 42 46 44 47 YES 15 1 4 2 6 3 8 5 10 7 12 9 14 11 17 13 19 16 21 18 23 20 25 22 27 24 29 26 31 28 33 30 35 32 37 34 39 36 41 38 43 40 45 42 47 44 49 46 51 48 53 50 55 52 5...
result:
ok Correct (1560 test cases)
Test #19:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
394 97 4606 92 2317 101 1713 95 450 101 4990 107 624 101 5044 106 5518 96 4512 106 5504 108 2743 104 5299 94 4316 101 351 104 3142 108 5757 102 5124 94 4321 108 4240 105 5425 90 3955 100 4903 106 2385 104 5337 96 4505 99 4838 97 4652 92 4171 100 4892 110 4994 110 747 98 4718 94 2159 105 2314 94 4343...
output:
YES 1 2 5 3 7 4 9 6 11 8 13 10 15 12 17 14 19 16 21 18 23 20 25 22 27 24 29 26 31 28 33 30 35 32 37 34 39 36 41 38 43 40 45 42 47 44 49 46 51 48 53 50 55 52 57 54 59 56 61 58 63 60 65 62 67 64 69 66 71 68 73 70 75 72 77 74 79 76 81 78 83 80 85 82 87 84 89 86 91 88 93 90 95 92 96 94 97 YES 14 1 4 2 6...
result:
ok Correct (394 test cases)
Test #20:
score: 0
Accepted
time: 1ms
memory: 3744kb
input:
99 210 9276 194 18622 201 20031 203 3130 198 19422 208 21421 206 9196 193 18498 206 11194 199 5647 203 20420 210 21831 202 20196 197 19198 202 20206 195 18812 192 18333 198 19459 202 511 194 18637 200 13168 208 15719 200 2279 203 16405 197 19198 204 20604 191 18132 190 17894 209 16449 191 10417 209 ...
output:
YES 1 2 3 4 5 6 7 8 9 10 11 12 13 14 17 15 16 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 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 86 85 88 87 90 89 92 91 94 93 96 95 98 97 100 99 102 ...
result:
ok Correct (99 test cases)
Test #21:
score: 0
Accepted
time: 1ms
memory: 3728kb
input:
44 301 44995 295 43213 305 46241 310 2815 300 13643 297 43917 302 38708 305 2407 302 45409 300 44710 305 46199 298 38380 293 42668 299 44402 297 43920 303 45636 295 43239 301 45092 299 44477 295 43217 310 30914 296 43508 291 42168 290 3004 303 11092 301 45111 310 9447 292 11065 302 45301 294 42917 3...
output:
YES 9 1 4 2 6 3 8 5 11 7 13 10 15 12 17 14 19 16 21 18 23 20 25 22 27 24 29 26 31 28 33 30 35 32 37 34 39 36 41 38 43 40 45 42 47 44 49 46 51 48 53 50 55 52 57 54 59 56 61 58 63 60 65 62 67 64 69 66 71 68 73 70 75 72 77 74 79 76 81 78 83 80 85 82 87 84 89 86 91 88 93 90 95 92 97 94 99 96 101 98 103 ...
result:
ok Correct (44 test cases)
Test #22:
score: 0
Accepted
time: 1ms
memory: 3732kb
input:
25 393 24865 409 83229 409 83228 397 78466 397 78497 398 78795 406 28894 405 81636 398 78818 398 78811 399 79193 391 76050 401 36783 392 76615 391 76045 410 83631 403 44100 404 10805 392 76436 400 79791 403 80797 400 59101 390 75675 397 22854 392 76435
output:
YES 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 61 59 60 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 97 98 99 100 101 ...
result:
ok Correct (25 test cases)
Test #23:
score: 0
Accepted
time: 1ms
memory: 3652kb
input:
15 509 129152 490 119746 492 120563 501 125131 504 93193 508 100551 494 121519 500 124497 503 126000 491 1479 506 127718 505 127003 505 127085 498 123702 510 129719
output:
NO NO NO NO YES 214 1 4 2 6 3 8 5 10 7 12 9 14 11 16 13 18 15 20 17 22 19 24 21 26 23 28 25 30 27 32 29 34 31 36 33 38 35 40 37 42 39 44 41 46 43 48 45 50 47 52 49 54 51 56 53 58 55 60 57 62 59 64 61 66 63 68 65 70 67 72 69 74 71 76 73 78 75 80 77 82 79 84 81 86 83 88 85 90 87 92 89 94 91 96 93 98 9...
result:
ok Correct (15 test cases)
Test #24:
score: 0
Accepted
time: 1ms
memory: 3720kb
input:
11 608 169179 599 5916 600 31395 608 18910 601 180167 605 182399 603 181198 591 60281 595 176408 609 185083 596 177270
output:
YES 72 1 4 2 6 3 8 5 10 7 12 9 14 11 16 13 18 15 20 17 22 19 24 21 26 23 28 25 30 27 32 29 34 31 36 33 38 35 40 37 42 39 44 41 46 43 48 45 50 47 52 49 54 51 56 53 58 55 60 57 62 59 64 61 66 63 68 65 70 67 73 69 75 71 77 74 79 76 81 78 83 80 85 82 87 84 89 86 91 88 93 90 95 92 97 94 99 96 101 98 103 ...
result:
ok Correct (11 test cases)
Test #25:
score: 0
Accepted
time: 1ms
memory: 3728kb
input:
8 696 241511 701 129166 700 52365 695 240810 690 235929 694 240313 691 238246 704 247218
output:
YES 1 2 5 3 7 4 9 6 11 8 13 10 15 12 17 14 19 16 21 18 23 20 25 22 27 24 29 26 31 28 33 30 35 32 37 34 39 36 41 38 43 40 45 42 47 44 49 46 51 48 53 50 55 52 57 54 59 56 61 58 63 60 65 62 67 64 69 66 71 68 73 70 75 72 77 74 79 76 81 78 83 80 85 82 87 84 89 86 91 88 93 90 95 92 97 94 99 96 101 98 103 ...
result:
ok Correct (8 test cases)
Test #26:
score: 0
Accepted
time: 1ms
memory: 3728kb
input:
6 791 312045 802 247610 804 322553 806 324256 796 316408 791 95268
output:
YES 9 1 4 2 6 3 8 5 11 7 13 10 15 12 17 14 19 16 21 18 23 20 25 22 27 24 29 26 31 28 33 30 35 32 37 34 39 36 41 38 43 40 45 42 47 44 49 46 51 48 53 50 55 52 57 54 59 56 61 58 63 60 65 62 67 64 69 66 71 68 73 70 75 72 77 74 79 76 81 78 83 80 85 82 87 84 89 86 91 88 93 90 95 92 97 94 99 96 101 98 103 ...
result:
ok Correct (6 test cases)
Test #27:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
4 903 407183 895 399696 908 411720 893 397825
output:
NO NO NO YES 13 1 4 2 6 3 8 5 10 7 12 9 15 11 17 14 19 16 21 18 23 20 25 22 27 24 29 26 31 28 33 30 35 32 37 34 39 36 41 38 43 40 45 42 47 44 49 46 51 48 53 50 55 52 57 54 59 56 61 58 63 60 65 62 67 64 69 66 71 68 73 70 75 72 77 74 79 76 81 78 83 80 85 82 87 84 89 86 91 88 93 90 95 92 97 94 99 96 10...
result:
ok Correct (4 test cases)
Test #28:
score: 0
Accepted
time: 1ms
memory: 3820kb
input:
4 958 458261 945 445705 945 144602 958 457928
output:
NO NO YES 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 28 26 27 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 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 97 98 99 10...
result:
ok Correct (4 test cases)
Test #29:
score: 0
Accepted
time: 1ms
memory: 3724kb
input:
4 984 350686 983 88304 974 473788 981 480195
output:
YES 555 1 4 2 6 3 8 5 10 7 12 9 14 11 16 13 18 15 20 17 22 19 24 21 26 23 28 25 30 27 32 29 34 31 36 33 38 35 40 37 42 39 44 41 46 43 48 45 50 47 52 49 54 51 56 53 58 55 60 57 62 59 64 61 66 63 68 65 70 67 72 69 74 71 76 73 78 75 80 77 82 79 84 81 86 83 88 85 90 87 92 89 94 91 96 93 98 95 100 97 102...
result:
ok Correct (4 test cases)
Test #30:
score: 0
Accepted
time: 1ms
memory: 3656kb
input:
4 997 495998 994 493016 996 302206 991 490041
output:
YES 19 1 4 2 6 3 8 5 10 7 12 9 14 11 16 13 18 15 21 17 23 20 25 22 27 24 29 26 31 28 33 30 35 32 37 34 39 36 41 38 43 40 45 42 47 44 49 46 51 48 53 50 55 52 57 54 59 56 61 58 63 60 65 62 67 64 69 66 71 68 73 70 75 72 77 74 79 76 81 78 83 80 85 82 87 84 89 86 91 88 93 90 95 92 97 94 99 96 101 98 103 ...
result:
ok Correct (4 test cases)