QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#183975#4902. 聚会hos_lyric#36.363636 375ms12960kbC++144.3kb2023-09-20 05:48:102024-07-04 02:05:10

Judging History

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

  • [2024-07-04 02:05:10]
  • 评测
  • 测评结果：36.363636
  • 用时：375ms
  • 内存：12960kb
查看
  • [2023-09-20 05:48:10]
  • 提交

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 <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 N;
int counter;
bool used[3010][3010];
void add(int u, int v, int w) {
  ++counter;
  printf("%d %d %d\n", u, v, w);
  assert(1 <= u); assert(u <= N);
  assert(1 <= v); assert(v <= N);
  assert(1 <= w); assert(w <= N);
  assert(u != v); assert(!used[u][v]); used[u][v] = used[v][u] = true;
  assert(v != w); assert(!used[v][w]); used[v][w] = used[w][v] = true;
  assert(w != u); assert(!used[w][u]); used[w][u] = used[u][w] = true;
}

int M;
int mod(int u) {
  return ((u %= M) < 0) ? (u + M) : u;
}

int main() {
  for (; ~scanf("%d", &N); ) {
cerr<<"======== N = "<<N<<" ========"<<endl;
    assert(N % 6 == 1 || N % 6 == 3);
    counter = 0;
    memset(used, 0, sizeof(used));
    
    if (N >= 3) {
      M = N - 2;
      for (int u = 1; u < M; ++u) for (int v = u + 1; v < M; ++v) {
        const int w = mod(-(u + v));
        if (v < w) {
          add(u, v, w);
        }
      }
      
      /*
        remaining:
          (u, -u): matching
          (u, -2u): cycles
        -> 3 matchings
      */
      vector<pair<int, int>> mas[3];
      vector<int> vis(M, 0);
      for (int u = 1; u < M; ++u) if (!vis[u]) {
        vector<int> cyc;
        for (int v = u; !vis[v]; v = mod(-2 * v)) {
          vis[v] = u;
          cyc.push_back(v);
        }
// cerr<<"cyc = "<<cyc<<endl;
        const int len = cyc.size();
        if (len & 1) {
          for (int j = 0; j < len; ++j) {
            assert(!vis[M - cyc[j]]);
            vis[M - cyc[j]] = u;
          }
          for (int j = 0; j < len - 1; ++j) {
            mas[j & 1].emplace_back(cyc[j], cyc[(j + 1) % len]);
            mas[j & 1].emplace_back(M - cyc[j], M - cyc[(j + 1) % len]);
          }
          mas[2].emplace_back(cyc[0], cyc[len - 1]);
          mas[2].emplace_back(M - cyc[0], M - cyc[len - 1]);
          mas[0].emplace_back(cyc[len - 1], M - cyc[len - 1]);
          mas[1].emplace_back(cyc[0], M - cyc[0]);
          for (int j = 1; j < len - 1; ++j) {
            mas[2].emplace_back(cyc[j], M - cyc[j]);
          }
        } else if (vis[M - u]) {
          for (int j = 0; j < len; ++j) {
            mas[j & 1].emplace_back(cyc[j], cyc[(j + 1) % len]);
          }
          for (int j = 0; j < len / 2; ++j) {
            assert(cyc[j + len / 2] == M - cyc[j]);
            mas[2].emplace_back(cyc[j], cyc[j + len / 2]);
          }
        } else {
          for (int j = 0; j < len; ++j) {
            assert(!vis[M - cyc[j]]);
            vis[M - cyc[j]] = u;
          }
          for (int j = 0; j < len; ++j) {
            mas[j & 1].emplace_back(cyc[j], cyc[(j + 1) % len]);
            mas[j & 1].emplace_back(M - cyc[j], M - cyc[(j + 1) % len]);
          }
          for (int j = 0; j < len; ++j) {
            mas[2].emplace_back(cyc[j], M - cyc[j]);
          }
        }
      }
      for (int k = 0; k < 3; ++k) {
        for (const auto &e : mas[k]) {
          add(M + k, e.first, e.second);
        }
      }
      add(M, M + 1, M + 2);
    }
    
    assert(counter == N * (N - 1) / 6);
  }
  return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 9.09091
Accepted

Test #1:

score: 9.09091
Accepted
time: 0ms
memory: 12516kb

input:

1

output:

result:

ok accepted

Test #2:

score: 0
Accepted
time: 0ms
memory: 12912kb

input:

3

output:

1 2 3

result:

ok accepted

Test #3:

score: 0
Accepted
time: 2ms
memory: 12644kb

input:

7

output:

5 1 3
5 4 2
6 3 4
6 2 1
7 1 4
7 3 2
5 6 7

result:

ok accepted

Test #4:

score: 0
Accepted
time: 0ms
memory: 12652kb

input:

15

output:

1 2 10
1 3 9
1 4 8
1 5 7
2 3 8
2 4 7
2 5 6
3 4 6
3 11 12
4 10 12
5 9 12
5 10 11
6 8 12
6 9 11
7 8 11
7 9 10
13 1 11
13 4 5
13 3 7
13 12 2
13 9 8
13 10 6
14 11 4
14 5 3
14 7 12
14 2 9
14 8 10
14 6 1
15 1 12
15 11 2
15 4 9
15 5 8
15 3 10
15 7 6
13 14 15

result:

ok accepted

Test #5:

score: 0
Accepted
time: 3ms
memory: 12680kb

input:

31

output:

1 2 26
1 3 25
1 4 24
1 5 23
1 6 22
1 7 21
1 8 20
1 9 19
1 10 18
1 11 17
1 12 16
1 13 15
2 3 24
2 4 23
2 5 22
2 6 21
2 7 20
2 8 19
2 9 18
2 10 17
2 11 16
2 12 15
2 13 14
3 4 22
3 5 21
3 6 20
3 7 19
3 8 18
3 9 17
3 10 16
3 11 15
3 12 14
3 27 28
4 5 20
4 6 19
4 7 18
4 8 17
4 9 16
4 10 15
4 11 14
4 12 1...

result:

ok accepted

Test #6:

score: 0
Accepted
time: 0ms
memory: 12956kb

input:

63

output:

1 2 58
1 3 57
1 4 56
1 5 55
1 6 54
1 7 53
1 8 52
1 9 51
1 10 50
1 11 49
1 12 48
1 13 47
1 14 46
1 15 45
1 16 44
1 17 43
1 18 42
1 19 41
1 20 40
1 21 39
1 22 38
1 23 37
1 24 36
1 25 35
1 26 34
1 27 33
1 28 32
1 29 31
2 3 56
2 4 55
2 5 54
2 6 53
2 7 52
2 8 51
2 9 50
2 10 49
2 11 48
2 12 47
2 13 46
2 1...

result:

ok accepted

Test #7:

score: 0
Accepted
time: 0ms
memory: 12736kb

input:

127

output:

1 2 122
1 3 121
1 4 120
1 5 119
1 6 118
1 7 117
1 8 116
1 9 115
1 10 114
1 11 113
1 12 112
1 13 111
1 14 110
1 15 109
1 16 108
1 17 107
1 18 106
1 19 105
1 20 104
1 21 103
1 22 102
1 23 101
1 24 100
1 25 99
1 26 98
1 27 97
1 28 96
1 29 95
1 30 94
1 31 93
1 32 92
1 33 91
1 34 90
1 35 89
1 36 88
1 37 ...

result:

ok accepted

Test #8:

score: 0
Accepted
time: 5ms
memory: 12912kb

input:

255

output:

1 2 250
1 3 249
1 4 248
1 5 247
1 6 246
1 7 245
1 8 244
1 9 243
1 10 242
1 11 241
1 12 240
1 13 239
1 14 238
1 15 237
1 16 236
1 17 235
1 18 234
1 19 233
1 20 232
1 21 231
1 22 230
1 23 229
1 24 228
1 25 227
1 26 226
1 27 225
1 28 224
1 29 223
1 30 222
1 31 221
1 32 220
1 33 219
1 34 218
1 35 217
1 ...

result:

ok accepted

Test #9:

score: 0
Accepted
time: 9ms
memory: 12744kb

input:

511

output:

1 2 506
1 3 505
1 4 504
1 5 503
1 6 502
1 7 501
1 8 500
1 9 499
1 10 498
1 11 497
1 12 496
1 13 495
1 14 494
1 15 493
1 16 492
1 17 491
1 18 490
1 19 489
1 20 488
1 21 487
1 22 486
1 23 485
1 24 484
1 25 483
1 26 482
1 27 481
1 28 480
1 29 479
1 30 478
1 31 477
1 32 476
1 33 475
1 34 474
1 35 473
1 ...

result:

ok accepted

Test #10:

score: 0
Accepted
time: 42ms
memory: 12752kb

input:

1023

output:

1 2 1018
1 3 1017
1 4 1016
1 5 1015
1 6 1014
1 7 1013
1 8 1012
1 9 1011
1 10 1010
1 11 1009
1 12 1008
1 13 1007
1 14 1006
1 15 1005
1 16 1004
1 17 1003
1 18 1002
1 19 1001
1 20 1000
1 21 999
1 22 998
1 23 997
1 24 996
1 25 995
1 26 994
1 27 993
1 28 992
1 29 991
1 30 990
1 31 989
1 32 988
1 33 987
1...

result:

ok accepted

Test #11:

score: 0
Accepted
time: 172ms
memory: 12644kb

input:

2047

output:

1 2 2042
1 3 2041
1 4 2040
1 5 2039
1 6 2038
1 7 2037
1 8 2036
1 9 2035
1 10 2034
1 11 2033
1 12 2032
1 13 2031
1 14 2030
1 15 2029
1 16 2028
1 17 2027
1 18 2026
1 19 2025
1 20 2024
1 21 2023
1 22 2022
1 23 2021
1 24 2020
1 25 2019
1 26 2018
1 27 2017
1 28 2016
1 29 2015
1 30 2014
1 31 2013
1 32 201...

result:

ok accepted

Subtask #2:

score: 9.09091
Accepted

Test #12:

score: 9.09091
Accepted
time: 3ms
memory: 12644kb

input:

3

output:

1 2 3

result:

ok accepted

Test #13:

score: 0
Accepted
time: 0ms
memory: 12948kb

input:

9

output:

1 2 4
3 5 6
7 1 5
7 4 6
7 2 3
8 5 4
8 6 2
8 3 1
9 1 6
9 5 2
9 4 3
7 8 9

result:

ok accepted

Test #14:

score: 0
Accepted
time: 2ms
memory: 12644kb

input:

27

output:

1 2 22
1 3 21
1 4 20
1 5 19
1 6 18
1 7 17
1 8 16
1 9 15
1 10 14
1 11 13
2 3 20
2 4 19
2 5 18
2 6 17
2 7 16
2 8 15
2 9 14
2 10 13
2 11 12
3 4 18
3 5 17
3 6 16
3 7 15
3 8 14
3 9 13
3 10 12
3 23 24
4 5 16
4 6 15
4 7 14
4 8 13
4 9 12
4 10 11
4 22 24
5 6 14
5 7 13
5 8 12
5 9 11
5 21 24
5 22 23
6 7 12
6 8...

result:

ok accepted

Test #15:

score: 0
Accepted
time: 3ms
memory: 12624kb

input:

81

output:

1 2 76
1 3 75
1 4 74
1 5 73
1 6 72
1 7 71
1 8 70
1 9 69
1 10 68
1 11 67
1 12 66
1 13 65
1 14 64
1 15 63
1 16 62
1 17 61
1 18 60
1 19 59
1 20 58
1 21 57
1 22 56
1 23 55
1 24 54
1 25 53
1 26 52
1 27 51
1 28 50
1 29 49
1 30 48
1 31 47
1 32 46
1 33 45
1 34 44
1 35 43
1 36 42
1 37 41
1 38 40
2 3 74
2 4 7...

result:

ok accepted

Test #16:

score: 0
Accepted
time: 2ms
memory: 12648kb

input:

243

output:

1 2 238
1 3 237
1 4 236
1 5 235
1 6 234
1 7 233
1 8 232
1 9 231
1 10 230
1 11 229
1 12 228
1 13 227
1 14 226
1 15 225
1 16 224
1 17 223
1 18 222
1 19 221
1 20 220
1 21 219
1 22 218
1 23 217
1 24 216
1 25 215
1 26 214
1 27 213
1 28 212
1 29 211
1 30 210
1 31 209
1 32 208
1 33 207
1 34 206
1 35 205
1 ...

result:

ok accepted

Test #17:

score: 0
Accepted
time: 20ms
memory: 12680kb

input:

729

output:

1 2 724
1 3 723
1 4 722
1 5 721
1 6 720
1 7 719
1 8 718
1 9 717
1 10 716
1 11 715
1 12 714
1 13 713
1 14 712
1 15 711
1 16 710
1 17 709
1 18 708
1 19 707
1 20 706
1 21 705
1 22 704
1 23 703
1 24 702
1 25 701
1 26 700
1 27 699
1 28 698
1 29 697
1 30 696
1 31 695
1 32 694
1 33 693
1 34 692
1 35 691
1 ...

result:

ok accepted

Test #18:

score: 0
Accepted
time: 197ms
memory: 12784kb

input:

2187

output:

1 2 2182
1 3 2181
1 4 2180
1 5 2179
1 6 2178
1 7 2177
1 8 2176
1 9 2175
1 10 2174
1 11 2173
1 12 2172
1 13 2171
1 14 2170
1 15 2169
1 16 2168
1 17 2167
1 18 2166
1 19 2165
1 20 2164
1 21 2163
1 22 2162
1 23 2161
1 24 2160
1 25 2159
1 26 2158
1 27 2157
1 28 2156
1 29 2155
1 30 2154
1 31 2153
1 32 215...

result:

ok accepted

Subtask #3:

score: 9.09091
Accepted

Test #19:

score: 9.09091
Accepted
time: 0ms
memory: 12556kb

input:

1

output:

result:

ok accepted

Test #20:

score: 0
Accepted
time: 3ms
memory: 12960kb

input:

25

output:

1 2 20
1 3 19
1 4 18
1 5 17
1 6 16
1 7 15
1 8 14
1 9 13
1 10 12
2 3 18
2 4 17
2 5 16
2 6 15
2 7 14
2 8 13
2 9 12
2 10 11
3 4 16
3 5 15
3 6 14
3 7 13
3 8 12
3 9 11
3 21 22
4 5 14
4 6 13
4 7 12
4 8 11
4 9 10
4 20 22
5 6 12
5 7 11
5 8 10
5 19 22
5 20 21
6 7 10
6 8 9
6 18 22
6 19 21
7 17 22
7 18 21
7 19...

result:

ok accepted

Test #21:

score: 0
Accepted
time: 375ms
memory: 12756kb

input:

2977

output:

1 2 2972
1 3 2971
1 4 2970
1 5 2969
1 6 2968
1 7 2967
1 8 2966
1 9 2965
1 10 2964
1 11 2963
1 12 2962
1 13 2961
1 14 2960
1 15 2959
1 16 2958
1 17 2957
1 18 2956
1 19 2955
1 20 2954
1 21 2953
1 22 2952
1 23 2951
1 24 2950
1 25 2949
1 26 2948
1 27 2947
1 28 2946
1 29 2945
1 30 2944
1 31 2943
1 32 294...

result:

ok accepted

Test #22:

score: 0
Accepted
time: 364ms
memory: 12808kb

input:

2953

output:

1 2 2948
1 3 2947
1 4 2946
1 5 2945
1 6 2944
1 7 2943
1 8 2942
1 9 2941
1 10 2940
1 11 2939
1 12 2938
1 13 2937
1 14 2936
1 15 2935
1 16 2934
1 17 2933
1 18 2932
1 19 2931
1 20 2930
1 21 2929
1 22 2928
1 23 2927
1 24 2926
1 25 2925
1 26 2924
1 27 2923
1 28 2922
1 29 2921
1 30 2920
1 31 2919
1 32 291...

result:

ok accepted

Test #23:

score: 0
Accepted
time: 133ms
memory: 12704kb

input:

1777

output:

1 2 1772
1 3 1771
1 4 1770
1 5 1769
1 6 1768
1 7 1767
1 8 1766
1 9 1765
1 10 1764
1 11 1763
1 12 1762
1 13 1761
1 14 1760
1 15 1759
1 16 1758
1 17 1757
1 18 1756
1 19 1755
1 20 1754
1 21 1753
1 22 1752
1 23 1751
1 24 1750
1 25 1749
1 26 1748
1 27 1747
1 28 1746
1 29 1745
1 30 1744
1 31 1743
1 32 174...

result:

ok accepted
lled after throwing an instance of 'std::out_of_range'
  what():  basic_string::substr: __pos (which is 13) > this->size() (which is 0)

Subtask #4:

score: 9.09091
Accepted

Test #24:

score: 9.09091
Accepted
time: 0ms
memory: 12680kb

input:

7

output:

5 1 3
5 4 2
6 3 4
6 2 1
7 1 4
7 3 2
5 6 7

result:

ok accepted

Test #25:

score: 0
Accepted
time: 0ms
memory: 12708kb

input:

31

output:

1 2 26
1 3 25
1 4 24
1 5 23
1 6 22
1 7 21
1 8 20
1 9 19
1 10 18
1 11 17
1 12 16
1 13 15
2 3 24
2 4 23
2 5 22
2 6 21
2 7 20
2 8 19
2 9 18
2 10 17
2 11 16
2 12 15
2 13 14
3 4 22
3 5 21
3 6 20
3 7 19
3 8 18
3 9 17
3 10 16
3 11 15
3 12 14
3 27 28
4 5 20
4 6 19
4 7 18
4 8 17
4 9 16
4 10 15
4 11 14
4 12 1...

result:

ok accepted

Test #26:

score: 0
Accepted
time: 167ms
memory: 12720kb

input:

2983

output:

1 2 2978
1 3 2977
1 4 2976
1 5 2975
1 6 2974
1 7 2973
1 8 2972
1 9 2971
1 10 2970
1 11 2969
1 12 2968
1 13 2967
1 14 2966
1 15 2965
1 16 2964
1 17 2963
1 18 2962
1 19 2961
1 20 2960
1 21 2959
1 22 2958
1 23 2957
1 24 2956
1 25 2955
1 26 2954
1 27 2953
1 28 2952
1 29 2951
1 30 2950
1 31 2949
1 32 294...

result:

ok accepted

Test #27:

score: 0
Accepted
time: 155ms
memory: 12788kb

input:

2959

output:

1 2 2954
1 3 2953
1 4 2952
1 5 2951
1 6 2950
1 7 2949
1 8 2948
1 9 2947
1 10 2946
1 11 2945
1 12 2944
1 13 2943
1 14 2942
1 15 2941
1 16 2940
1 17 2939
1 18 2938
1 19 2937
1 20 2936
1 21 2935
1 22 2934
1 23 2933
1 24 2932
1 25 2931
1 26 2930
1 27 2929
1 28 2928
1 29 2927
1 30 2926
1 31 2925
1 32 292...

result:

ok accepted

Test #28:

score: 0
Accepted
time: 16ms
memory: 12688kb

input:

871

output:

1 2 866
1 3 865
1 4 864
1 5 863
1 6 862
1 7 861
1 8 860
1 9 859
1 10 858
1 11 857
1 12 856
1 13 855
1 14 854
1 15 853
1 16 852
1 17 851
1 18 850
1 19 849
1 20 848
1 21 847
1 22 846
1 23 845
1 24 844
1 25 843
1 26 842
1 27 841
1 28 840
1 29 839
1 30 838
1 31 837
1 32 836
1 33 835
1 34 834
1 35 833
1 ...

result:

ok accepted

Subtask #5:

score: 0
Checker Judgement Failed

Test #29:

score: 9.09091
Accepted
time: 0ms
memory: 12596kb

input:

13

output:

1 2 8
1 3 7
1 4 6
2 3 6
2 4 5
3 9 10
4 8 10
5 7 10
5 8 9
6 7 9
11 1 9
11 10 2
11 4 3
11 7 8
11 5 6
12 9 4
12 2 7
12 3 5
12 8 6
12 1 10
13 1 5
13 10 6
13 9 2
13 4 7
13 3 8
11 12 13

result:

ok accepted

Test #30:

score: 0
Accepted
time: 0ms
memory: 12648kb

input:

37

output:

1 2 32
1 3 31
1 4 30
1 5 29
1 6 28
1 7 27
1 8 26
1 9 25
1 10 24
1 11 23
1 12 22
1 13 21
1 14 20
1 15 19
1 16 18
2 3 30
2 4 29
2 5 28
2 6 27
2 7 26
2 8 25
2 9 24
2 10 23
2 11 22
2 12 21
2 13 20
2 14 19
2 15 18
2 16 17
3 4 28
3 5 27
3 6 26
3 7 25
3 8 24
3 9 23
3 10 22
3 11 21
3 12 20
3 13 19
3 14 18
3...

result:

ok accepted

Test #31:

score: 0
Accepted
time: 159ms
memory: 12744kb

input:

2989

output:

1 2 2984
1 3 2983
1 4 2982
1 5 2981
1 6 2980
1 7 2979
1 8 2978
1 9 2977
1 10 2976
1 11 2975
1 12 2974
1 13 2973
1 14 2972
1 15 2971
1 16 2970
1 17 2969
1 18 2968
1 19 2967
1 20 2966
1 21 2965
1 22 2964
1 23 2963
1 24 2962
1 25 2961
1 26 2960
1 27 2959
1 28 2958
1 29 2957
1 30 2956
1 31 2955
1 32 295...

result:

ok accepted

Test #32:

score: -9.09091
Checker Judgement Failed

input:

2965

output:

result:

Subtask #6:

score: 0
Judgement Failed

Test #34:

score: 0
Judgement Failed

input:

19

output:

result:

Subtask #7:

score: 0
Judgement Failed

Test #39:

score: 0
Judgement Failed

input:

3

output:

result:

Subtask #8:

score: 0
Judgement Failed

Test #44:

score: 0
Judgement Failed

input:

21

output:

result:

Subtask #9:

score: 0
Judgement Failed

Test #49:

score: 0
Judgement Failed

input:

9

output:

result:

Subtask #10:

score: 0
Judgement Failed

Test #54:

score: 0
Judgement Failed

input:

15

output:

result:

Subtask #11:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

0%
English 繁體中文 简体中文

Server Time: 2024-12-02 15:24:21 | OpenSource Project