QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#300148#5529. Most Annoying Constructive Problemhos_lyricAC ✓10ms3824kbC++148.0kb2024-01-07 19:12:212024-01-07 19:12:21

Judging History

你现在查看的是最新测评结果

  • [2024-01-07 19:12:21]
  • 评测
  • 测评结果:AC
  • 用时:10ms
  • 内存:3824kb
  • [2024-01-07 19:12:21]
  • 提交

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;
}

详细

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)