QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #815300 | #9870. Items | zzuqy | WA | 6767ms | 8660kb | C++14 | 1.6kb | 2024-12-15 12:00:20 | 2024-12-15 12:00:20 |
Judging History
answer
#include<bits/stdc++.h>
#define N 100009
#define D 10009
#define int long long
using namespace std;
int n,m,k,a[N];
bitset<D*2>ok,ok2;
int aabs(int x,int y){
return max(x-y,y-x);
}
void solve(){
scanf("%lld%lld",&n,&m);
unordered_set<int>s;int k=0;
for(int i=1;i<=n;i++){
int x;scanf("%lld",&x);
s.insert(x);
}
for(auto i:s)a[++k]=i;
sort(a+1,a+k+1);
a[0]=-10000000000000;
a[k+1]=10000000000000;
int tmp=m/n;
int pos=0;
for(int i=1;i<=k;i++){
if(a[i]<=tmp&&tmp<a[i+1])pos=i;
}
int c=0;
for(int i=0;i<=n;i++){
if(aabs(a[pos]*i+a[pos+1]*(n-i),m)<aabs(a[pos]*c+a[pos+1]*(n-c),m))c=i;
}
m-=a[pos]*c+a[pos+1]*(n-c);
if(aabs(m,0)>D){
cout<<"No"<<endl;
return;
}
ok.reset();
ok[m+D]=1;
vector<int>p,q;
for(int i=1;i<=k;i++){
if(aabs(a[i],a[pos])<D/2-1&&i!=pos)p.push_back(a[i]-a[pos]);
if(aabs(a[i],a[pos+1])<D/2-1&&i!=pos+1)q.push_back(a[i]-a[pos+1]);
}
if(ok[D]){
cout<<"Yes"<<endl;
return;
}
if(p.size())
for(int i=1;i<=min(100ll*n/(int)p.size(),c);i++){
ok2.reset();
for(auto x:p){
if(x<0)ok2|=(ok<<(-x));
else ok2|=(ok>>x);
}
ok=ok2|ok;
if(ok[D]){
cout<<"Yes"<<endl;
return;
}
}
if(q.size())
for(int i=1;i<=min(100ll*n/(int)q.size(),n-c);i++){
ok2.reset();
for(auto x:q){
if(x<0)ok2|=(ok<<(-x));
else ok2|=(ok>>x);
}
ok=ok2|ok;
if(ok[D]){
cout<<"Yes"<<endl;
return;
}
}
cout<<"No"<<endl;
}
signed main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
int t;scanf("%lld",&t);
while(t--)solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3740kb
input:
4 5 25 0 0 0 0 5 5 11 4 4 4 5 5 5 0 1 2 3 4 5 5 25 0 1 2 3 4
output:
Yes No No No
result:
ok 4 token(s): yes count is 1, no count is 3
Test #2:
score: 0
Accepted
time: 5ms
memory: 3672kb
input:
1314 1 0 0 1 0 1 1 1 0 1 1 1 2 0 0 0 2 0 0 1 2 0 0 2 2 0 1 0 2 0 1 1 2 0 1 2 2 0 2 0 2 0 2 1 2 0 2 2 2 1 0 0 2 1 0 1 2 1 0 2 2 1 1 0 2 1 1 1 2 1 1 2 2 1 2 0 2 1 2 1 2 1 2 2 2 2 0 0 2 2 0 1 2 2 0 2 2 2 1 0 2 2 1 1 2 2 1 2 2 2 2 0 2 2 2 1 2 2 2 2 2 3 0 0 2 3 0 1 2 3 0 2 2 3 1 0 2 3 1 1 2 3 1 2 2 3 2 0...
output:
Yes No No Yes Yes Yes Yes Yes No No Yes No No No Yes No Yes No No No No No No Yes Yes Yes Yes Yes Yes Yes No No No No No No Yes No Yes No No No Yes No No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No No No Yes No No No Yes No No No Yes Yes Yes...
result:
ok 1314 token(s): yes count is 732, no count is 582
Test #3:
score: 0
Accepted
time: 28ms
memory: 3692kb
input:
10000 4 1 0 0 0 0 4 1 0 0 0 1 4 1 0 0 0 2 4 1 0 0 0 3 4 1 0 0 0 4 4 1 0 0 1 0 4 1 0 0 1 1 4 1 0 0 1 2 4 1 0 0 1 3 4 1 0 0 1 4 4 1 0 0 2 0 4 1 0 0 2 1 4 1 0 0 2 2 4 1 0 0 2 3 4 1 0 0 2 4 4 1 0 0 3 0 4 1 0 0 3 1 4 1 0 0 3 2 4 1 0 0 3 3 4 1 0 0 3 4 4 1 0 0 4 0 4 1 0 0 4 1 4 1 0 0 4 2 4 1 0 0 4 3 4 1 0 ...
output:
No Yes No No No Yes Yes Yes Yes Yes No Yes No No No No Yes No No No No Yes No No No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No Yes No No No Yes Yes Yes Yes Yes No Yes No No No No Yes No No No No Yes No No No No Yes No No No Yes Yes Yes Yes ...
result:
ok 10000 token(s): yes count is 6168, no count is 3832
Test #4:
score: 0
Accepted
time: 3ms
memory: 3936kb
input:
1612 5 0 0 0 0 0 0 5 0 1 1 1 1 1 5 0 0 1 1 1 1 5 0 2 2 2 2 2 5 0 0 2 2 2 2 5 0 1 2 2 2 2 5 0 0 1 2 2 2 5 0 3 3 3 3 3 5 0 0 3 3 3 3 5 0 1 3 3 3 3 5 0 0 1 3 3 3 5 0 2 3 3 3 3 5 0 0 2 3 3 3 5 0 1 2 3 3 3 5 0 0 1 2 3 3 5 0 4 4 4 4 4 5 0 0 4 4 4 4 5 0 1 4 4 4 4 5 0 0 1 4 4 4 5 0 2 4 4 4 4 5 0 0 2 4 4 4 5...
output:
Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No No No Yes No No No Yes No No No Yes No No No Yes No No No Yes No No No Yes No No No...
result:
ok 1612 token(s): yes count is 864, no count is 748
Test #5:
score: 0
Accepted
time: 20ms
memory: 3612kb
input:
4662 6 0 0 0 0 0 0 0 6 0 1 1 1 1 1 1 6 0 0 1 1 1 1 1 6 0 2 2 2 2 2 2 6 0 0 2 2 2 2 2 6 0 1 2 2 2 2 2 6 0 0 1 2 2 2 2 6 0 3 3 3 3 3 3 6 0 0 3 3 3 3 3 6 0 1 3 3 3 3 3 6 0 0 1 3 3 3 3 6 0 2 3 3 3 3 3 6 0 0 2 3 3 3 3 6 0 1 2 3 3 3 3 6 0 0 1 2 3 3 3 6 0 4 4 4 4 4 4 6 0 0 4 4 4 4 4 6 0 1 4 4 4 4 4 6 0 0 1...
output:
Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No...
result:
ok 4662 token(s): yes count is 2730, no count is 1932
Test #6:
score: 0
Accepted
time: 4489ms
memory: 8660kb
input:
1 100000 9999999999 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 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 9...
output:
No
result:
ok NO
Test #7:
score: 0
Accepted
time: 81ms
memory: 3748kb
input:
10000 10 3 5 9 0 1 1 10 0 6 3 2 10 22 5 7 0 0 10 5 6 2 7 8 10 67 7 7 7 4 0 8 10 10 5 10 10 56 1 6 5 3 0 7 3 5 8 9 10 43 4 4 0 3 3 4 1 3 0 0 10 91 0 6 6 9 2 3 10 8 6 0 10 2 5 1 4 0 10 9 2 3 2 9 10 73 8 5 6 10 10 2 8 10 4 8 10 36 10 2 5 1 3 6 7 3 7 10 10 90 3 4 5 10 7 7 3 5 1 6 10 20 9 4 3 1 1 6 8 1 5...
output:
Yes Yes Yes Yes No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No Yes No Yes Yes Yes Yes Yes Yes Yes Yes No Yes Yes Yes Yes Yes Yes Yes Yes No Yes Yes Yes No Yes Yes No No Yes Yes Yes Yes Yes Yes No No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No Yes No No Yes Yes Yes Yes Yes Yes Yes Y...
result:
ok 10000 token(s): yes count is 8663, no count is 1337
Test #8:
score: 0
Accepted
time: 99ms
memory: 3676kb
input:
1000 100 8921 54 82 23 19 31 95 88 97 10 26 61 50 49 10 4 29 90 60 20 73 45 95 44 96 47 20 24 39 15 35 78 24 78 60 100 36 63 53 70 42 61 78 38 64 0 38 80 99 9 77 68 84 71 75 63 57 38 32 1 74 75 53 0 18 74 80 79 49 31 90 61 81 28 16 72 81 58 76 33 68 76 15 96 65 59 27 0 75 47 85 8 27 55 36 28 49 33 6...
output:
Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No Yes Yes No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Ye...
result:
ok 1000 token(s): yes count is 983, no count is 17
Test #9:
score: 0
Accepted
time: 30ms
memory: 3744kb
input:
100 1000 822190 824 147 580 931 944 411 499 248 16 807 817 933 344 801 776 172 736 814 298 944 324 901 146 149 653 850 431 224 670 778 918 957 418 847 787 256 313 675 189 372 527 630 518 214 430 962 549 142 419 388 461 227 471 337 436 172 941 944 785 49 630 943 896 819 188 976 230 896 638 30 935 787...
output:
Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes ...
result:
ok 100 token(s): yes count is 100, no count is 0
Test #10:
score: 0
Accepted
time: 22ms
memory: 4072kb
input:
10 10000 36452743 3219 2049 8923 2370 670 7258 1630 4309 5307 7756 4017 7973 4652 3806 8536 3319 6721 8996 9923 4793 944 7181 1293 6733 5461 9146 5187 3302 2405 8747 9377 2121 5977 3321 3013 1359 8648 5541 3697 4971 7303 7762 2025 695 7336 9420 6617 1496 1680 3299 8682 7302 5303 6835 8207 6786 7868 ...
output:
Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes
result:
ok 10 token(s): yes count is 10, no count is 0
Test #11:
score: 0
Accepted
time: 27ms
memory: 6660kb
input:
1 100000 7132922381 65268 98569 49569 42441 31688 75146 41758 82634 22278 88725 35755 66423 15583 10748 68319 15051 44705 17431 24789 61906 39753 44681 94285 31076 91405 10918 99048 31599 1684 65254 25364 73214 82162 76373 68973 12878 18037 43668 53394 65187 77671 17544 99819 82666 83485 20807 71773...
output:
Yes
result:
ok YES
Test #12:
score: 0
Accepted
time: 253ms
memory: 3704kb
input:
1000 100 1132 81 98 41 61 59 50 62 42 59 68 59 74 100 75 29 4 53 38 21 95 77 46 92 93 26 29 41 85 58 40 27 99 9 85 10 24 46 19 17 51 47 15 14 2 24 11 5 79 7 94 97 62 9 83 53 99 55 37 50 1 82 42 41 28 48 53 24 64 61 40 34 51 41 67 82 86 5 74 38 59 96 0 96 73 31 15 90 32 82 41 97 78 57 42 53 46 14 16 ...
output:
Yes No Yes Yes Yes Yes Yes Yes Yes Yes No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No No Yes No Yes No Yes No Yes Yes Yes No Yes Yes No No Yes Yes No Yes No No Yes Yes Yes No No No Yes Yes No Yes Yes Yes Yes Yes No Yes Yes No No No Yes Yes Yes No No Yes Yes No Yes Yes Yes No Yes No No No Yes ...
result:
ok 1000 token(s): yes count is 670, no count is 330
Test #13:
score: 0
Accepted
time: 1388ms
memory: 3936kb
input:
10 10000 96020464 4552 8968 5192 360 6728 6496 4760 336 2520 2176 6544 6200 2064 1016 7312 7264 136 5832 6344 3064 3064 9712 8648 7000 80 576 2152 8944 2208 9176 7224 1704 2272 8096 7944 5664 9848 3232 9376 4200 6824 8872 8336 9728 4216 4488 5248 4816 1352 3208 4104 5344 9432 6672 1992 2520 4016 248...
output:
Yes Yes No No Yes Yes No No No Yes
result:
ok 10 token(s): yes count is 5, no count is 5
Test #14:
score: 0
Accepted
time: 6ms
memory: 3672kb
input:
1 100000 178306281 49588 24794 99176 0 74382 49588 49588 74382 74382 49588 99176 99176 24794 74382 49588 0 0 49588 99176 24794 24794 0 74382 74382 74382 74382 24794 0 74382 49588 49588 49588 99176 74382 0 49588 99176 24794 24794 24794 49588 74382 99176 0 74382 49588 74382 49588 99176 99176 0 74382 7...
output:
No
result:
ok NO
Test #15:
score: 0
Accepted
time: 6ms
memory: 3672kb
input:
1 100000 1557960515 83410 32925 26340 98775 96580 89995 50485 19755 85605 46095 98775 10975 17560 92190 48290 92190 96580 24145 59265 0 35120 59265 68045 2195 43900 28535 35120 70240 48290 54875 26340 26340 92190 2195 83410 79020 89995 94385 61460 30730 59265 8780 37315 76825 81215 76825 92190 72435...
output:
Yes
result:
ok YES
Test #16:
score: 0
Accepted
time: 4464ms
memory: 3780kb
input:
1 100000 683435046 63546 42534 53499 18258 51714 76398 54519 11475 67830 99144 62220 52326 13719 56355 50388 62934 52224 35190 11730 867 71757 20961 9639 24174 69513 14637 23613 11169 34782 93738 72420 58242 25806 58038 17748 47073 93177 94809 97104 96798 68850 10812 64923 88791 57375 44676 62730 28...
output:
No
result:
ok NO
Test #17:
score: 0
Accepted
time: 6767ms
memory: 4044kb
input:
1 100000 4237125909 92100 88908 42480 31656 75660 9876 2280 51072 4584 45660 55536 62532 39432 15840 86832 86124 97068 36432 85632 6840 76656 4212 86184 11496 99336 56148 6372 8040 39960 85620 55392 58212 6684 1812 94176 52392 2400 41520 86940 68892 90888 1092 20028 76656 86676 23820 32388 16596 399...
output:
No
result:
ok NO
Test #18:
score: 0
Accepted
time: 6ms
memory: 3628kb
input:
1 100000 7060472559 21072 80337 60582 98775 88239 18438 22389 56631 55314 67167 28974 81654 96141 65850 52680 46095 5268 1317 10536 61899 21072 57948 1317 51363 11853 73752 86922 31608 3951 79020 40827 39510 86922 31608 68484 27657 63216 11853 1317 67167 51363 34242 89556 17121 5268 44778 76386 9614...
output:
Yes
result:
ok YES
Test #19:
score: 0
Accepted
time: 142ms
memory: 3696kb
input:
1000 100 3950 56 68 81 56 81 56 81 81 56 81 81 81 56 56 68 68 81 81 81 56 56 68 68 68 81 68 81 68 56 68 68 56 81 81 81 81 68 56 56 81 56 68 56 56 81 56 81 56 68 68 81 81 68 56 56 68 68 81 68 68 81 68 81 81 68 56 56 68 81 56 68 56 81 68 68 68 56 68 81 81 68 81 56 68 68 56 56 81 81 81 81 56 56 56 56 8...
output:
No No Yes Yes Yes Yes No No Yes No No Yes Yes Yes No No Yes Yes Yes Yes No Yes No Yes Yes Yes No No Yes Yes Yes No Yes No No Yes Yes Yes Yes No Yes Yes Yes Yes Yes No No Yes Yes No Yes Yes No Yes Yes No Yes Yes Yes Yes No No Yes Yes No No Yes No Yes Yes Yes Yes No Yes Yes Yes No Yes Yes Yes Yes No Y...
result:
ok 1000 token(s): yes count is 597, no count is 403
Test #20:
score: 0
Accepted
time: 34ms
memory: 3632kb
input:
10 10000 34796587 1660 9050 6984 8300 4980 6984 9050 8300 4980 8300 6984 6984 9050 6984 9050 8300 9050 9050 9050 6984 6984 8300 1660 9050 6640 1660 6984 9960 6984 9050 4980 9050 9050 1660 6984 3320 6984 6984 9050 1660 9050 6984 3320 6984 3320 3320 3320 6984 3320 6984 4980 9050 8300 8300 6984 6984 66...
output:
No No Yes No No Yes Yes Yes Yes Yes
result:
ok 10 token(s): yes count is 6, no count is 4
Test #21:
score: 0
Accepted
time: 70ms
memory: 3748kb
input:
1 100000 9147040951 44280 77118 92394 77118 92394 22140 77118 88560 22140 77118 92394 92394 77118 88560 66420 22140 92394 88560 22140 92394 92394 77118 92394 66420 77118 88560 77118 77118 77118 22140 88560 66420 22140 77118 88560 77118 77118 92394 77118 88560 77118 77118 92394 77118 92394 92394 7711...
output:
No
result:
ok NO
Test #22:
score: -100
Wrong Answer
time: 6ms
memory: 3672kb
input:
1 100000 6448741768 96237 64834 96237 64834 96237 46792 96237 46792 96237 96237 96237 64834 96237 96237 64834 64834 96237 96237 64834 96237 96237 64834 70188 64834 64834 64834 96237 64834 64834 96237 46792 64834 96237 96237 64834 93584 96237 96237 23396 96237 93584 64834 70188 64834 23396 96237 9623...
output:
No
result:
wrong answer expected YES, found NO [1st token]