QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#189882 | #1807. Distribute the Bars | KKT89 | AC ✓ | 16ms | 29616kb | C++17 | 2.7kb | 2023-09-28 01:16:17 | 2023-09-28 01:16:17 |
Judging History
answer
#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <cstdio>
#include <ctime>
#include <assert.h>
#include <chrono>
#include <random>
#include <numeric>
#include <set>
#include <deque>
#include <stack>
#include <sstream>
#include <utility>
#include <cstring>
#include <unordered_map>
#include <unordered_set>
#include <tuple>
#include <array>
#include <bitset>
using namespace std;
typedef long long int ll;
typedef unsigned long long ull;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
return (ull)rng() % B;
}
inline ll time() {
return static_cast<long double>(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count()) * 1e-9;
}
const int N = 1e6;
bool is_not_prime[N];
vector<int> res[N];
int main(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
int n; cin >> n;
is_not_prime[0] = is_not_prime[1] = true;
for(int i=2;i<N;i++){
if(!is_not_prime[i]){
for(int j=i+i;j<N;j+=i){
is_not_prime[j]=true;
}
}
}
if(!is_not_prime[n]){
printf("-1\n");
return 0;
}
else if(n%2==0){
printf("%d\n",n/2);
int cur=1;
for(int i=0;i<n/2;i++){
res[i].push_back(cur);
cur+=2;
}
for(int i=n/2-1;i>=0;i--){
res[i].push_back(cur);
cur+=2;
}
for(int i=0;i<n/2;i++){
printf("%d",res[i].size());
for(int j=0;j<res[i].size();j++){
printf(" %d",res[i][j]);
}
printf("\n");
}
}
else{
int d;
for(int i=2;i*i<=n;i++){
if(n%i==0){
d=i;
break;
}
}
printf("%d\n",d);
int cur=1;
int id=0;
for(int i=0;i<d;i++){
for(int j=0;j<d;j++){
res[(id+j)%d].push_back(cur+2*d*j);
}
cur+=2;
id++;
}
cur=2*d*d+1;
while(cur<2*n+1){
for(int i=0;i<d;i++){
res[i].push_back(cur);
cur+=2;
}
for(int i=d-1;i>=0;i--){
res[i].push_back(cur);
cur+=2;
}
}
for(int i=0;i<d;i++){
printf("%d",res[i].size());
int sum=0;
for(int j=0;j<res[i].size();j++){
printf(" %d",res[i][j]);
sum+=res[i][j];
}
printf("\n");
}
}
}
详细
Test #1:
score: 100
Accepted
time: 10ms
memory: 28168kb
input:
4
output:
2 2 1 7 2 3 5
result:
ok OK (2 groups)
Test #2:
score: 0
Accepted
time: 3ms
memory: 27980kb
input:
2
output:
-1
result:
ok OK (impossible)
Test #3:
score: 0
Accepted
time: 8ms
memory: 27932kb
input:
3
output:
-1
result:
ok OK (impossible)
Test #4:
score: 0
Accepted
time: 5ms
memory: 28136kb
input:
1659
output:
3 553 1 15 11 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: 7ms
memory: 28104kb
input:
8941
output:
-1
result:
ok OK (impossible)
Test #6:
score: 0
Accepted
time: 3ms
memory: 28072kb
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: 27932kb
input:
5
output:
-1
result:
ok OK (impossible)
Test #8:
score: 0
Accepted
time: 3ms
memory: 28040kb
input:
9
output:
3 3 1 15 11 3 7 3 17 3 13 9 5
result:
ok OK (3 groups)
Test #9:
score: 0
Accepted
time: 7ms
memory: 28048kb
input:
25
output:
5 5 1 43 35 27 19 5 11 3 45 37 29 5 21 13 5 47 39 5 31 23 15 7 49 5 41 33 25 17 9
result:
ok OK (5 groups)
Test #10:
score: 0
Accepted
time: 10ms
memory: 28064kb
input:
143
output:
11 13 1 223 203 183 163 143 123 103 83 63 43 243 285 13 23 3 225 205 185 165 145 125 105 85 65 245 283 13 45 25 5 227 207 187 167 147 127 107 87 247 281 13 67 47 27 7 229 209 189 169 149 129 109 249 279 13 89 69 49 29 9 231 211 191 171 151 131 251 277 13 111 91 71 51 31 11 233 213 193 173 153 253 27...
result:
ok OK (11 groups)
Test #11:
score: 0
Accepted
time: 11ms
memory: 28472kb
input:
85849
output:
293 293 1 171115 170531 169947 169363 168779 168195 167611 167027 166443 165859 165275 164691 164107 163523 162939 162355 161771 161187 160603 160019 159435 158851 158267 157683 157099 156515 155931 155347 154763 154179 153595 153011 152427 151843 151259 150675 150091 149507 148923 148339 147755 147...
result:
ok OK (293 groups)
Test #12:
score: 0
Accepted
time: 3ms
memory: 28160kb
input:
99991
output:
-1
result:
ok OK (impossible)
Test #13:
score: 0
Accepted
time: 6ms
memory: 28368kb
input:
99997
output:
19 5263 1 687 651 615 579 543 507 471 435 399 363 327 291 255 219 183 147 111 75 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 2...
result:
ok OK (19 groups)
Test #14:
score: 0
Accepted
time: 8ms
memory: 29616kb
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: 6ms
memory: 28396kb
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: 29048kb
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: 16ms
memory: 29444kb
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: 11ms
memory: 28160kb
input:
16831
output:
-1
result:
ok OK (impossible)
Test #19:
score: 0
Accepted
time: 8ms
memory: 28460kb
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: 3ms
memory: 28164kb
input:
28979
output:
-1
result:
ok OK (impossible)
Test #21:
score: 0
Accepted
time: 7ms
memory: 27936kb
input:
20173
output:
-1
result:
ok OK (impossible)
Test #22:
score: 0
Accepted
time: 7ms
memory: 27884kb
input:
78401
output:
-1
result:
ok OK (impossible)
Test #23:
score: 0
Accepted
time: 5ms
memory: 27936kb
input:
52067
output:
-1
result:
ok OK (impossible)
Test #24:
score: 0
Accepted
time: 3ms
memory: 27988kb
input:
94727
output:
-1
result:
ok OK (impossible)
Test #25:
score: 0
Accepted
time: 8ms
memory: 28420kb
input:
35657
output:
181 197 1 65163 64803 64443 64083 63723 63363 63003 62643 62283 61923 61563 61203 60843 60483 60123 59763 59403 59043 58683 58323 57963 57603 57243 56883 56523 56163 55803 55443 55083 54723 54363 54003 53643 53283 52923 52563 52203 51843 51483 51123 50763 50403 50043 49683 49323 48963 48603 48243 47...
result:
ok OK (181 groups)
Test #26:
score: 0
Accepted
time: 9ms
memory: 28436kb
input:
41449
output:
181 229 1 65163 64803 64443 64083 63723 63363 63003 62643 62283 61923 61563 61203 60843 60483 60123 59763 59403 59043 58683 58323 57963 57603 57243 56883 56523 56163 55803 55443 55083 54723 54363 54003 53643 53283 52923 52563 52203 51843 51483 51123 50763 50403 50043 49683 49323 48963 48603 48243 47...
result:
ok OK (181 groups)
Test #27:
score: 0
Accepted
time: 3ms
memory: 28356kb
input:
7367
output:
53 139 1 5515 5411 5307 5203 5099 4995 4891 4787 4683 4579 4475 4371 4267 4163 4059 3955 3851 3747 3643 3539 3435 3331 3227 3123 3019 2915 2811 2707 2603 2499 2395 2291 2187 2083 1979 1875 1771 1667 1563 1459 1355 1251 1147 1043 939 835 731 627 523 419 315 211 5619 5829 5831 6041 6043 6253 6255 6465...
result:
ok OK (53 groups)
Test #28:
score: 0
Accepted
time: 3ms
memory: 28204kb
input:
12191
output:
73 167 1 10515 10371 10227 10083 9939 9795 9651 9507 9363 9219 9075 8931 8787 8643 8499 8355 8211 8067 7923 7779 7635 7491 7347 7203 7059 6915 6771 6627 6483 6339 6195 6051 5907 5763 5619 5475 5331 5187 5043 4899 4755 4611 4467 4323 4179 4035 3891 3747 3603 3459 3315 3171 3027 2883 2739 2595 2451 23...
result:
ok OK (73 groups)
Test #29:
score: 0
Accepted
time: 6ms
memory: 28312kb
input:
43847
output:
163 269 1 52815 52491 52167 51843 51519 51195 50871 50547 50223 49899 49575 49251 48927 48603 48279 47955 47631 47307 46983 46659 46335 46011 45687 45363 45039 44715 44391 44067 43743 43419 43095 42771 42447 42123 41799 41475 41151 40827 40503 40179 39855 39531 39207 38883 38559 38235 37911 37587 37...
result:
ok OK (163 groups)
Test #30:
score: 0
Accepted
time: 7ms
memory: 28188kb
input:
20819
output:
109 191 1 23547 23331 23115 22899 22683 22467 22251 22035 21819 21603 21387 21171 20955 20739 20523 20307 20091 19875 19659 19443 19227 19011 18795 18579 18363 18147 17931 17715 17499 17283 17067 16851 16635 16419 16203 15987 15771 15555 15339 15123 14907 14691 14475 14259 14043 13827 13611 13395 13...
result:
ok OK (109 groups)
Test #31:
score: 0
Accepted
time: 7ms
memory: 28140kb
input:
9943
output:
61 163 1 7323 7203 7083 6963 6843 6723 6603 6483 6363 6243 6123 6003 5883 5763 5643 5523 5403 5283 5163 5043 4923 4803 4683 4563 4443 4323 4203 4083 3963 3843 3723 3603 3483 3363 3243 3123 3003 2883 2763 2643 2523 2403 2283 2163 2043 1923 1803 1683 1563 1443 1323 1203 1083 963 843 723 603 483 363 24...
result:
ok OK (61 groups)
Test #32:
score: 0
Accepted
time: 3ms
memory: 28080kb
input:
1369
output:
37 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 1011 939 867 795 723 651 579 507 435 363 291 219 147 37 75 3 2669 2597 2525 2453 2381 2309 2237 2165 2093 2021 1949 1877 1805 1733 1661 1589 1517 1445 1373 1301 1229 1157 1085 1...
result:
ok OK (37 groups)
Test #33:
score: 0
Accepted
time: 0ms
memory: 28176kb
input:
6241
output:
79 79 1 12327 12171 12015 11859 11703 11547 11391 11235 11079 10923 10767 10611 10455 10299 10143 9987 9831 9675 9519 9363 9207 9051 8895 8739 8583 8427 8271 8115 7959 7803 7647 7491 7335 7179 7023 6867 6711 6555 6399 6243 6087 5931 5775 5619 5463 5307 5151 4995 4839 4683 4527 4371 4215 4059 3903 37...
result:
ok OK (79 groups)
Test #34:
score: 0
Accepted
time: 3ms
memory: 27956kb
input:
841
output:
29 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 1349 1293 1237 1181 1125 1069 1013 957 901 845 789 733 677 621 565 509 453 397 341 285 229 173 29 117 61 5 1631 1575 1519 1463 1407 135...
result:
ok OK (29 groups)
Test #35:
score: 0
Accepted
time: 14ms
memory: 28436kb
input:
69169
output:
263 263 1 137815 137291 136767 136243 135719 135195 134671 134147 133623 133099 132575 132051 131527 131003 130479 129955 129431 128907 128383 127859 127335 126811 126287 125763 125239 124715 124191 123667 123143 122619 122095 121571 121047 120523 119999 119475 118951 118427 117903 117379 116855 116...
result:
ok OK (263 groups)
Test #36:
score: 0
Accepted
time: 10ms
memory: 28220kb
input:
121
output:
11 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 153 11 133 113 93 73 53 33 13 235 215 195 175 11 1...
result:
ok OK (11 groups)