QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#61600#1807. Distribute the BarsBooksnowAC ✓12ms8772kbC++141.9kb2022-11-14 11:04:322022-11-14 11:04:34

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-14 11:04:34]
  • 评测
  • 测评结果:AC
  • 用时:12ms
  • 内存:8772kb
  • [2022-11-14 11:04:32]
  • 提交

answer

#include <bits/stdc++.h>
#define st first
#define nd second
#define db double
#define re register
#define pb push_back
#define mk make_pair
#define int long long
#define ldb long double
#define pii pair<int, int>
#define ull unsigned long long
#define mst(a, b) memset(a, b, sizeof(a))
using namespace std;
const int N = 1e5 + 10, M = 4e2, lim = 1e5, mod = 998244353;
inline int read()
{
  int s = 0, w = 1;
  char ch = getchar();
  while(ch < '0' || ch > '9') { if(ch == '-') w *= -1; ch = getchar(); }
  while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
  return s * w;
}
int n;
int c[M][M];
bool vis[N];
vector<int> pri;
vector<int> ans[N];
inline void initial()
{
  for(re int i = 2; i <= lim; i++){
    if(!vis[i]){
      pri.pb(i);
      for(re int j = 2; i * j <= lim; j++) vis[i * j] = true;
    }
  }
}
signed main()
{
  initial();
  n = read();
  if(!vis[n]) puts("-1"), exit(0);
  if(n & 1){
    int a, b;
    for(re int p : pri)
      if(n % p == 0) { a = p, b = n / p; break; }
    vector<pii> rec;
    int m = a * (b - a), k = 0;
    for(re int i = 1, j = m; i <= m / 2; i++, j--) rec.pb(mk(i * 2 - 1, j * 2 - 1));
    for(re pii x : rec) ans[k].pb(x.st), ans[k].pb(x.nd), k = (k + 1) % a;
    for(re int i = m + 1, x = 1, y = 1; i <= n; i++){
      c[x][y] = i * 2 - 1, y += 1;
      if(y > a) x += 1, y = 1;
    }
    for(re int i = 1; i <= a; i++){ //进行分组
      int x = 1, y = i, id = i - 1;
      for(re int j = 1; j <= a; j++){
        ans[id].pb(c[x][y]), x += 1, y += 1;
        if(y > a) y = 1;
      }
    }
    printf("%lld\n", a);
    for(re int i = 0; i < a; i++, puts("")){
      printf("%lld ", ans[i].size());
      for(re int x : ans[i]) printf("%lld ", x);
    }
  }
  else{
    printf("%lld\n", n / 2);
    for(re int i = 1, j = n; i <= n / 2; i++, j--)
      printf("2 %lld %lld\n", (i * 2 - 1), (j * 2 - 1));
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 6232kb

input:

4

output:

2
2 1 7
2 3 5

result:

ok OK (2 groups)

Test #2:

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

input:

2

output:

-1

result:

ok OK (impossible)

Test #3:

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

input:

3

output:

-1

result:

ok OK (impossible)

Test #4:

score: 0
Accepted
time: 6ms
memory: 6768kb

input:

1659

output:

3
553 1 3299 7 3293 13 3287 19 3281 25 3275 31 3269 37 3263 43 3257 49 3251 55 3245 61 3239 67 3233 73 3227 79 3221 85 3215 91 3209 97 3203 103 3197 109 3191 115 3185 121 3179 127 3173 133 3167 139 3161 145 3155 151 3149 157 3143 163 3137 169 3131 175 3125 181 3119 187 3113 193 3107 199 3101 205 309...

result:

ok OK (3 groups)

Test #5:

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

input:

8941

output:

-1

result:

ok OK (impossible)

Test #6:

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

input:

458

output:

229
2 1 915
2 3 913
2 5 911
2 7 909
2 9 907
2 11 905
2 13 903
2 15 901
2 17 899
2 19 897
2 21 895
2 23 893
2 25 891
2 27 889
2 29 887
2 31 885
2 33 883
2 35 881
2 37 879
2 39 877
2 41 875
2 43 873
2 45 871
2 47 869
2 49 867
2 51 865
2 53 863
2 55 861
2 57 859
2 59 857
2 61 855
2 63 853
2 65 851
2 67...

result:

ok OK (229 groups)

Test #7:

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

input:

5

output:

-1

result:

ok OK (impossible)

Test #8:

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

input:

9

output:

3
3 1 9 17 
3 3 11 13 
3 5 7 15 

result:

ok OK (3 groups)

Test #9:

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

input:

25

output:

5
5 1 13 25 37 49 
5 3 15 27 39 41 
5 5 17 29 31 43 
5 7 19 21 33 45 
5 9 11 23 35 47 

result:

ok OK (5 groups)

Test #10:

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

input:

143

output:

11
13 1 43 45 69 93 117 141 165 189 213 237 261 285 
13 3 41 47 71 95 119 143 167 191 215 239 263 265 
13 5 39 49 73 97 121 145 169 193 217 241 243 267 
13 7 37 51 75 99 123 147 171 195 219 221 245 269 
13 9 35 53 77 101 125 149 173 197 199 223 247 271 
13 11 33 55 79 103 127 151 175 177 201 225 249...

result:

ok OK (11 groups)

Test #11:

score: 0
Accepted
time: 8ms
memory: 8036kb

input:

85849

output:

293
293 1 589 1177 1765 2353 2941 3529 4117 4705 5293 5881 6469 7057 7645 8233 8821 9409 9997 10585 11173 11761 12349 12937 13525 14113 14701 15289 15877 16465 17053 17641 18229 18817 19405 19993 20581 21169 21757 22345 22933 23521 24109 24697 25285 25873 26461 27049 27637 28225 28813 29401 29989 30...

result:

ok OK (293 groups)

Test #12:

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

input:

99991

output:

-1

result:

ok OK (impossible)

Test #13:

score: 0
Accepted
time: 7ms
memory: 8772kb

input:

99997

output:

19
5263 1 199271 39 199233 77 199195 115 199157 153 199119 191 199081 229 199043 267 199005 305 198967 343 198929 381 198891 419 198853 457 198815 495 198777 533 198739 571 198701 609 198663 647 198625 685 198587 723 198549 761 198511 799 198473 837 198435 875 198397 913 198359 951 198321 989 198283...

result:

ok OK (19 groups)

Test #14:

score: 0
Accepted
time: 6ms
memory: 7008kb

input:

100000

output:

50000
2 1 199999
2 3 199997
2 5 199995
2 7 199993
2 9 199991
2 11 199989
2 13 199987
2 15 199985
2 17 199983
2 19 199981
2 21 199979
2 23 199977
2 25 199975
2 27 199973
2 29 199971
2 31 199969
2 33 199967
2 35 199965
2 37 199963
2 39 199961
2 41 199959
2 43 199957
2 45 199955
2 47 199953
2 49 199951...

result:

ok OK (50000 groups)

Test #15:

score: 0
Accepted
time: 8ms
memory: 6080kb

input:

28454

output:

14227
2 1 56907
2 3 56905
2 5 56903
2 7 56901
2 9 56899
2 11 56897
2 13 56895
2 15 56893
2 17 56891
2 19 56889
2 21 56887
2 23 56885
2 25 56883
2 27 56881
2 29 56879
2 31 56877
2 33 56875
2 35 56873
2 37 56871
2 39 56869
2 41 56867
2 43 56865
2 45 56863
2 47 56861
2 49 56859
2 51 56857
2 53 56855
2 ...

result:

ok OK (14227 groups)

Test #16:

score: 0
Accepted
time: 12ms
memory: 6204kb

input:

64338

output:

32169
2 1 128675
2 3 128673
2 5 128671
2 7 128669
2 9 128667
2 11 128665
2 13 128663
2 15 128661
2 17 128659
2 19 128657
2 21 128655
2 23 128653
2 25 128651
2 27 128649
2 29 128647
2 31 128645
2 33 128643
2 35 128641
2 37 128639
2 39 128637
2 41 128635
2 43 128633
2 45 128631
2 47 128629
2 49 128627...

result:

ok OK (32169 groups)

Test #17:

score: 0
Accepted
time: 8ms
memory: 6684kb

input:

88078

output:

44039
2 1 176155
2 3 176153
2 5 176151
2 7 176149
2 9 176147
2 11 176145
2 13 176143
2 15 176141
2 17 176139
2 19 176137
2 21 176135
2 23 176133
2 25 176131
2 27 176129
2 29 176127
2 31 176125
2 33 176123
2 35 176121
2 37 176119
2 39 176117
2 41 176115
2 43 176113
2 45 176111
2 47 176109
2 49 176107...

result:

ok OK (44039 groups)

Test #18:

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

input:

16831

output:

-1

result:

ok OK (impossible)

Test #19:

score: 0
Accepted
time: 6ms
memory: 6240kb

input:

10880

output:

5440
2 1 21759
2 3 21757
2 5 21755
2 7 21753
2 9 21751
2 11 21749
2 13 21747
2 15 21745
2 17 21743
2 19 21741
2 21 21739
2 23 21737
2 25 21735
2 27 21733
2 29 21731
2 31 21729
2 33 21727
2 35 21725
2 37 21723
2 39 21721
2 41 21719
2 43 21717
2 45 21715
2 47 21713
2 49 21711
2 51 21709
2 53 21707
2 5...

result:

ok OK (5440 groups)

Test #20:

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

input:

28979

output:

-1

result:

ok OK (impossible)

Test #21:

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

input:

20173

output:

-1

result:

ok OK (impossible)

Test #22:

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

input:

78401

output:

-1

result:

ok OK (impossible)

Test #23:

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

input:

52067

output:

-1

result:

ok OK (impossible)

Test #24:

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

input:

94727

output:

-1

result:

ok OK (impossible)

Test #25:

score: 0
Accepted
time: 4ms
memory: 7072kb

input:

35657

output:

181
197 1 5791 363 5429 725 5067 1087 4705 1449 4343 1811 3981 2173 3619 2535 3257 5793 6157 6521 6885 7249 7613 7977 8341 8705 9069 9433 9797 10161 10525 10889 11253 11617 11981 12345 12709 13073 13437 13801 14165 14529 14893 15257 15621 15985 16349 16713 17077 17441 17805 18169 18533 18897 19261 1...

result:

ok OK (181 groups)

Test #26:

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

input:

41449

output:

181
229 1 17375 363 17013 725 16651 1087 16289 1449 15927 1811 15565 2173 15203 2535 14841 2897 14479 3259 14117 3621 13755 3983 13393 4345 13031 4707 12669 5069 12307 5431 11945 5793 11583 6155 11221 6517 10859 6879 10497 7241 10135 7603 9773 7965 9411 8327 9049 17377 17741 18105 18469 18833 19197 ...

result:

ok OK (181 groups)

Test #27:

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

input:

7367

output:

53
139 1 9115 107 9009 213 8903 319 8797 425 8691 531 8585 637 8479 743 8373 849 8267 955 8161 1061 8055 1167 7949 1273 7843 1379 7737 1485 7631 1591 7525 1697 7419 1803 7313 1909 7207 2015 7101 2121 6995 2227 6889 2333 6783 2439 6677 2545 6571 2651 6465 2757 6359 2863 6253 2969 6147 3075 6041 3181 ...

result:

ok OK (53 groups)

Test #28:

score: 0
Accepted
time: 7ms
memory: 7576kb

input:

12191

output:

73
167 1 13723 147 13577 293 13431 439 13285 585 13139 731 12993 877 12847 1023 12701 1169 12555 1315 12409 1461 12263 1607 12117 1753 11971 1899 11825 2045 11679 2191 11533 2337 11387 2483 11241 2629 11095 2775 10949 2921 10803 3067 10657 3213 10511 3359 10365 3505 10219 3651 10073 3797 9927 3943 9...

result:

ok OK (73 groups)

Test #29:

score: 0
Accepted
time: 1ms
memory: 7420kb

input:

43847

output:

163
269 1 34555 327 34229 653 33903 979 33577 1305 33251 1631 32925 1957 32599 2283 32273 2609 31947 2935 31621 3261 31295 3587 30969 3913 30643 4239 30317 4565 29991 4891 29665 5217 29339 5543 29013 5869 28687 6195 28361 6521 28035 6847 27709 7173 27383 7499 27057 7825 26731 8151 26405 8477 26079 8...

result:

ok OK (163 groups)

Test #30:

score: 0
Accepted
time: 4ms
memory: 6528kb

input:

20819

output:

109
191 1 17875 219 17657 437 17439 655 17221 873 17003 1091 16785 1309 16567 1527 16349 1745 16131 1963 15913 2181 15695 2399 15477 2617 15259 2835 15041 3053 14823 3271 14605 3489 14387 3707 14169 3925 13951 4143 13733 4361 13515 4579 13297 4797 13079 5015 12861 5233 12643 5451 12425 5669 12207 58...

result:

ok OK (109 groups)

Test #31:

score: 0
Accepted
time: 6ms
memory: 6532kb

input:

9943

output:

61
163 1 12443 123 12321 245 12199 367 12077 489 11955 611 11833 733 11711 855 11589 977 11467 1099 11345 1221 11223 1343 11101 1465 10979 1587 10857 1709 10735 1831 10613 1953 10491 2075 10369 2197 10247 2319 10125 2441 10003 2563 9881 2685 9759 2807 9637 2929 9515 3051 9393 3173 9271 3295 9149 341...

result:

ok OK (61 groups)

Test #32:

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

input:

1369

output:

37
37 1 77 153 229 305 381 457 533 609 685 761 837 913 989 1065 1141 1217 1293 1369 1445 1521 1597 1673 1749 1825 1901 1977 2053 2129 2205 2281 2357 2433 2509 2585 2661 2737 
37 3 79 155 231 307 383 459 535 611 687 763 839 915 991 1067 1143 1219 1295 1371 1447 1523 1599 1675 1751 1827 1903 1979 2055...

result:

ok OK (37 groups)

Test #33:

score: 0
Accepted
time: 6ms
memory: 6904kb

input:

6241

output:

79
79 1 161 321 481 641 801 961 1121 1281 1441 1601 1761 1921 2081 2241 2401 2561 2721 2881 3041 3201 3361 3521 3681 3841 4001 4161 4321 4481 4641 4801 4961 5121 5281 5441 5601 5761 5921 6081 6241 6401 6561 6721 6881 7041 7201 7361 7521 7681 7841 8001 8161 8321 8481 8641 8801 8961 9121 9281 9441 960...

result:

ok OK (79 groups)

Test #34:

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

input:

841

output:

29
29 1 61 121 181 241 301 361 421 481 541 601 661 721 781 841 901 961 1021 1081 1141 1201 1261 1321 1381 1441 1501 1561 1621 1681 
29 3 63 123 183 243 303 363 423 483 543 603 663 723 783 843 903 963 1023 1083 1143 1203 1263 1323 1383 1443 1503 1563 1623 1625 
29 5 65 125 185 245 305 365 425 485 545...

result:

ok OK (29 groups)

Test #35:

score: 0
Accepted
time: 1ms
memory: 7916kb

input:

69169

output:

263
263 1 529 1057 1585 2113 2641 3169 3697 4225 4753 5281 5809 6337 6865 7393 7921 8449 8977 9505 10033 10561 11089 11617 12145 12673 13201 13729 14257 14785 15313 15841 16369 16897 17425 17953 18481 19009 19537 20065 20593 21121 21649 22177 22705 23233 23761 24289 24817 25345 25873 26401 26929 274...

result:

ok OK (263 groups)

Test #36:

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

input:

121

output:

11
11 1 25 49 73 97 121 145 169 193 217 241 
11 3 27 51 75 99 123 147 171 195 219 221 
11 5 29 53 77 101 125 149 173 197 199 223 
11 7 31 55 79 103 127 151 175 177 201 225 
11 9 33 57 81 105 129 153 155 179 203 227 
11 11 35 59 83 107 131 133 157 181 205 229 
11 13 37 61 85 109 111 135 159 183 207 2...

result:

ok OK (11 groups)