QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#18944#1807. Distribute the Barsforeverlasting#AC ✓17ms6536kbC++204.6kb2022-01-27 16:54:082022-05-06 03:22:00

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-06 03:22:00]
  • 评测
  • 测评结果:AC
  • 用时:17ms
  • 内存:6536kb
  • [2022-01-27 16:54:08]
  • 提交

answer

//2022.1.27 by ljz
//email [email protected]
//if you find any bug in my code
//please tell me
#include<bits/stdc++.h>
//#include<ext/pb_ds/tree_policy.hpp>
//#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
//using namespace __gnu_cxx;
#define res int
#define LL long long
#define Inf 0x3f3f3f3f
#define sup 0x7fffffff
#define inf 0x3f3f3f3f
#define INF 2000000000000000000
//#define unl __int128
#define eps 1e-10
#define RG
#define db double
#define pc(x) __builtin_popcount(x)
#define ctz(x) __builtin_ctz(x)
//#define pc(x) __builtin_popcountll(x)
typedef pair<int,int> Pair;
//#define poly vector<int>
#define mp make_pair
#define fi first
#define se second
#define pi acos(-1.0)
#define pb push_back
#define ull unsigned LL
#define uint unsigned int
#define lowbit(x) ((x)&-(x))
#define gc getchar
#define ld long db
//template <class T>using Tree=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
//inline int gc() {
//    static char buf[100000],*p1,*p2;
//    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
//}
//char sr[1<<21],z[20];
//int C=-1,Z=0;
//inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
//inline void print(RG LL x){
//    if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;
//    while(z[++Z]=x%10+48,x/=10);
//    while(sr[++C]=z[Z],--Z);
//}
template <typename T> inline void Read(T &x) {
    res c=gc();
    bool f=false;
    for(x=0;!isdigit(c);c=gc())if(c=='-')f=true;
    for(;isdigit(c);c=gc())x=x*10+c-'0';
    if(f)x=-x;
}
inline int read() {
    res s=0,ch=gc(),w=1;
    while(ch<'0'||ch>'9'){
        if(ch=='-')w=-1;
        else if(ch==EOF)break;
        ch=gc();
    }
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
    return s*w;
}
inline LL Read() {
    RG LL s=0;
    res ch=gc(),w=1;
    while(ch<'0'||ch>'9'){
        if(ch=='-')w=-1;
        else if(ch==EOF)break;
        ch=gc();
    }
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
    return s*w;
}
inline void write(RG __int128 x){
    if(x>10)write(x/10);
    putchar(int(x%10)+'0');
}
const int kcz=1000000007;
const int G=3,GI=332748118;
//inline void add(res &x,const res &y){
//    x+=y,x>=kcz?x-=kcz:1;
//}
//inline int Add(const res &x,const res &y){
//    return x+y>=kcz?x+y-kcz:x+y;
//}
//inline int mul(const res &x,const res &y){
//    return int(1ll*x*y%kcz);
//}
#define add(x,y) ((x)+=(y),(x)>=kcz?(x)-=kcz:1)
#define Add(x,y) ((x)+(y)>=kcz?(x)+(y)-kcz:(x)+(y))
#define mul(x,y) (int)((LL)(x)*(y)%kcz)
#define Mul(x,y,d) (int)((ull)(x)*(y)/(d)%kcz)
inline int qpow(res x,res y=kcz-2){
    res ret=1;
    while(y){
        if(y&1)ret=mul(ret,x);
        x=mul(x,x),y>>=1;
    }
    return ret;
}
inline int qpow(res x,res y,const res &ljc){
    res ret=1;
    while(y){
        if(y&1)ret=(int)(1ll*ret*x%ljc);
        x=(int)(1ll*x*x%ljc),y>>=1;
    }
    return ret;
}
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
//cloclim_t start=cloclim();
//inline void clim(){
//    if(1.0*(cloclim()-start)/CLOCKS_PER_SEC>0.1)exit(0);
//}
//2022.1.27 by ljz
//email [email protected]
//if you find any bug in my code
//please tell me
namespace MAIN{
    vector<int> A[100000+10];
    inline void MAIN(){
        res n=read();
        if(n==2){puts("-1");return;}
        if(n&1){
            res p=-1;
            for(res i=2;i*i<=n;i++){
                if(n%i==0){
                    p=i;break;
                }
            }
            if(p==-1){puts("-1");return;}
            for(res i=1;i<=p;i++){
                for(res j=1;j<=p;j++){
                    res t=(p-j+i)%p;
                    if(!t)t=p;
                    A[i].pb((t-1)*p+j);
                }
            }
            for(res i=p*p+1;i<=n;i+=2*p){
                for(res j=i;j<=i+p-1;j++){
                    A[j-i+1].pb(j);
                }
                for(res j=i+p;j<=i+2*p-1;j++){
                    A[i+2*p-j].pb(j);
                }
            }
            printf("%d\n",p);
            for(res i=1;i<=p;i++){
                printf("%d ",int(A[i].size()));
                for(auto x:A[i])printf("%d ",2*x-1);
                puts("");
            }
        }
        else {
            printf("%d\n",n/2);
            for(res i=1;i<=n/2;i++)printf("%d %d %d\n",2,2*i-1,2*(n-i)+1);
        }
    }
}
int main(){
//    srand(time(0));
//    freopen("1.in","r",stdin);
//    freopen("1.out","w",stdout);
    res Case=1;
    for(res T=1;T<=Case;T++)MAIN::MAIN();
//    Ot();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 6060kb

input:

4

output:

2
2 1 7
2 3 5

result:

ok OK (2 groups)

Test #2:

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

input:

2

output:

-1

result:

ok OK (impossible)

Test #3:

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

input:

3

output:

-1

result:

ok OK (impossible)

Test #4:

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

input:

1659

output:

3
553 13 9 5 19 29 31 41 43 53 55 65 67 77 79 89 91 101 103 113 115 125 127 137 139 149 151 161 163 173 175 185 187 197 199 209 211 221 223 233 235 245 247 257 259 269 271 281 283 293 295 305 307 317 319 329 331 341 343 353 355 365 367 377 379 389 391 401 403 413 415 425 427 437 439 449 451 461 463 ...

result:

ok OK (3 groups)

Test #5:

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

input:

8941

output:

-1

result:

ok OK (impossible)

Test #6:

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

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: 2ms
memory: 5940kb

input:

5

output:

-1

result:

ok OK (impossible)

Test #8:

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

input:

9

output:

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

result:

ok OK (3 groups)

Test #9:

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

input:

25

output:

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

result:

ok OK (5 groups)

Test #10:

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

input:

143

output:

11
13 221 201 181 161 141 121 101 81 61 41 21 243 285 
13 1 223 203 183 163 143 123 103 83 63 43 245 283 
13 23 3 225 205 185 165 145 125 105 85 65 247 281 
13 45 25 5 227 207 187 167 147 127 107 87 249 279 
13 67 47 27 7 229 209 189 169 149 129 109 251 277 
13 89 69 49 29 9 231 211 191 171 151 131 ...

result:

ok OK (11 groups)

Test #11:

score: 0
Accepted
time: 15ms
memory: 6524kb

input:

85849

output:

293
293 171113 170529 169945 169361 168777 168193 167609 167025 166441 165857 165273 164689 164105 163521 162937 162353 161769 161185 160601 160017 159433 158849 158265 157681 157097 156513 155929 155345 154761 154177 153593 153009 152425 151841 151257 150673 150089 149505 148921 148337 147753 14716...

result:

ok OK (293 groups)

Test #12:

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

input:

99991

output:

-1

result:

ok OK (impossible)

Test #13:

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

input:

99997

output:

19
5263 685 649 613 577 541 505 469 433 397 361 325 289 253 217 181 145 109 73 37 723 797 799 873 875 949 951 1025 1027 1101 1103 1177 1179 1253 1255 1329 1331 1405 1407 1481 1483 1557 1559 1633 1635 1709 1711 1785 1787 1861 1863 1937 1939 2013 2015 2089 2091 2165 2167 2241 2243 2317 2319 2393 2395 ...

result:

ok OK (19 groups)

Test #14:

score: 0
Accepted
time: 17ms
memory: 6048kb

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: 2ms
memory: 6064kb

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: 4ms
memory: 6008kb

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: 11ms
memory: 6064kb

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: 4ms
memory: 5916kb

input:

16831

output:

-1

result:

ok OK (impossible)

Test #19:

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

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: 2ms
memory: 5880kb

input:

28979

output:

-1

result:

ok OK (impossible)

Test #21:

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

input:

20173

output:

-1

result:

ok OK (impossible)

Test #22:

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

input:

78401

output:

-1

result:

ok OK (impossible)

Test #23:

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

input:

52067

output:

-1

result:

ok OK (impossible)

Test #24:

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

input:

94727

output:

-1

result:

ok OK (impossible)

Test #25:

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

input:

35657

output:

181
197 65161 64801 64441 64081 63721 63361 63001 62641 62281 61921 61561 61201 60841 60481 60121 59761 59401 59041 58681 58321 57961 57601 57241 56881 56521 56161 55801 55441 55081 54721 54361 54001 53641 53281 52921 52561 52201 51841 51481 51121 50761 50401 50041 49681 49321 48961 48601 48241 4788...

result:

ok OK (181 groups)

Test #26:

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

input:

41449

output:

181
229 65161 64801 64441 64081 63721 63361 63001 62641 62281 61921 61561 61201 60841 60481 60121 59761 59401 59041 58681 58321 57961 57601 57241 56881 56521 56161 55801 55441 55081 54721 54361 54001 53641 53281 52921 52561 52201 51841 51481 51121 50761 50401 50041 49681 49321 48961 48601 48241 4788...

result:

ok OK (181 groups)

Test #27:

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

input:

7367

output:

53
139 5513 5409 5305 5201 5097 4993 4889 4785 4681 4577 4473 4369 4265 4161 4057 3953 3849 3745 3641 3537 3433 3329 3225 3121 3017 2913 2809 2705 2601 2497 2393 2289 2185 2081 1977 1873 1769 1665 1561 1457 1353 1249 1145 1041 937 833 729 625 521 417 313 209 105 5619 5829 5831 6041 6043 6253 6255 64...

result:

ok OK (53 groups)

Test #28:

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

input:

12191

output:

73
167 10513 10369 10225 10081 9937 9793 9649 9505 9361 9217 9073 8929 8785 8641 8497 8353 8209 8065 7921 7777 7633 7489 7345 7201 7057 6913 6769 6625 6481 6337 6193 6049 5905 5761 5617 5473 5329 5185 5041 4897 4753 4609 4465 4321 4177 4033 3889 3745 3601 3457 3313 3169 3025 2881 2737 2593 2449 2305...

result:

ok OK (73 groups)

Test #29:

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

input:

43847

output:

163
269 52813 52489 52165 51841 51517 51193 50869 50545 50221 49897 49573 49249 48925 48601 48277 47953 47629 47305 46981 46657 46333 46009 45685 45361 45037 44713 44389 44065 43741 43417 43093 42769 42445 42121 41797 41473 41149 40825 40501 40177 39853 39529 39205 38881 38557 38233 37909 37585 3726...

result:

ok OK (163 groups)

Test #30:

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

input:

20819

output:

109
191 23545 23329 23113 22897 22681 22465 22249 22033 21817 21601 21385 21169 20953 20737 20521 20305 20089 19873 19657 19441 19225 19009 18793 18577 18361 18145 17929 17713 17497 17281 17065 16849 16633 16417 16201 15985 15769 15553 15337 15121 14905 14689 14473 14257 14041 13825 13609 13393 1317...

result:

ok OK (109 groups)

Test #31:

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

input:

9943

output:

61
163 7321 7201 7081 6961 6841 6721 6601 6481 6361 6241 6121 6001 5881 5761 5641 5521 5401 5281 5161 5041 4921 4801 4681 4561 4441 4321 4201 4081 3961 3841 3721 3601 3481 3361 3241 3121 3001 2881 2761 2641 2521 2401 2281 2161 2041 1921 1801 1681 1561 1441 1321 1201 1081 961 841 721 601 481 361 241 ...

result:

ok OK (61 groups)

Test #32:

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

input:

1369

output:

37
37 2665 2593 2521 2449 2377 2305 2233 2161 2089 2017 1945 1873 1801 1729 1657 1585 1513 1441 1369 1297 1225 1153 1081 1009 937 865 793 721 649 577 505 433 361 289 217 145 73 
37 1 2667 2595 2523 2451 2379 2307 2235 2163 2091 2019 1947 1875 1803 1731 1659 1587 1515 1443 1371 1299 1227 1155 1083 10...

result:

ok OK (37 groups)

Test #33:

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

input:

6241

output:

79
79 12325 12169 12013 11857 11701 11545 11389 11233 11077 10921 10765 10609 10453 10297 10141 9985 9829 9673 9517 9361 9205 9049 8893 8737 8581 8425 8269 8113 7957 7801 7645 7489 7333 7177 7021 6865 6709 6553 6397 6241 6085 5929 5773 5617 5461 5305 5149 4993 4837 4681 4525 4369 4213 4057 3901 3745...

result:

ok OK (79 groups)

Test #34:

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

input:

841

output:

29
29 1625 1569 1513 1457 1401 1345 1289 1233 1177 1121 1065 1009 953 897 841 785 729 673 617 561 505 449 393 337 281 225 169 113 57 
29 1 1627 1571 1515 1459 1403 1347 1291 1235 1179 1123 1067 1011 955 899 843 787 731 675 619 563 507 451 395 339 283 227 171 115 
29 59 3 1629 1573 1517 1461 1405 134...

result:

ok OK (29 groups)

Test #35:

score: 0
Accepted
time: 17ms
memory: 6536kb

input:

69169

output:

263
263 137813 137289 136765 136241 135717 135193 134669 134145 133621 133097 132573 132049 131525 131001 130477 129953 129429 128905 128381 127857 127333 126809 126285 125761 125237 124713 124189 123665 123141 122617 122093 121569 121045 120521 119997 119473 118949 118425 117901 117377 116853 11632...

result:

ok OK (263 groups)

Test #36:

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

input:

121

output:

11
11 221 201 181 161 141 121 101 81 61 41 21 
11 1 223 203 183 163 143 123 103 83 63 43 
11 23 3 225 205 185 165 145 125 105 85 65 
11 45 25 5 227 207 187 167 147 127 107 87 
11 67 47 27 7 229 209 189 169 149 129 109 
11 89 69 49 29 9 231 211 191 171 151 131 
11 111 91 71 51 31 11 233 213 193 173 1...

result:

ok OK (11 groups)