QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#709071 | #9527. A Brand New Geometric Problem | A_zjzj | AC ✓ | 215ms | 9372kb | C++14 | 2.0kb | 2024-11-04 11:11:22 | 2024-11-06 13:25:59 |
Judging History
你现在查看的是最新测评结果
- [2024-11-06 09:23:59]
- hack成功,自动添加数据
- (/hack/1137)
- [2024-11-04 16:55:58]
- hack成功,自动添加数据
- (/hack/1106)
- [2024-11-04 11:11:22]
- 提交
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e5+10;
ll S,M;
int n,m,id1[N],id2[N];
ll a[N];
int& getid(ll x){
if(x<=M/x)return id1[x];
else return id2[M/x];
}
vector<int>d[N];
vector<int>cur;
const ll INF=1e18;
ll ans=INF;
int t[N];
int cnt;
// void calc(){
// cnt++;
// ll sum=0;
// for(int x:cur)sum+=a[x];
// if(sum>S)return;
// int val=0;
// for(int l=0,r;l<cur.size();l=r){
// for(r=l+1;r<cur.size()&&cur[l]==cur[r];r++);
// int cnt=r-l;
// val+=min(cnt,t[cur[l]]);
// }
// ll ret=n-t[1]-val+cur.size()-val;
// if(S<sum+t[1])ret+=sum+t[1]-S;
// else ret+=S-sum-t[1];
// ans=min(ans,ret);
// }
int ljx;
void dfs(int x,int lim,int tot=0,ll sum=0,int val=0){
if(sum>S)return;
if(n-t[1]-val+tot-val+sum+t[1]-S>=ans)return;
if(n-t[1]-val+tot-val-35+S-sum-a[x]-t[1]>=ans)return;
if(x==1){
cnt++;
ll ret=n-t[1]-val+tot-val;
if(S<sum+t[1])ret+=sum+t[1]-S;
else ret+=S-sum-t[1];
ans=min(ans,ret);
return;
}
for(int i:d[x]){
if(i>lim)break;
bool flag=t[i]>0;
t[i]-=flag;
dfs(getid(a[x]/a[i]),i,tot+1,sum+a[i],val+flag);
t[i]+=flag;
}
}
int main(){
cin>>n>>S>>M;
vector<int>s;
for(int i=1;1ll*i*i<=M;i++){
if(M%i==0){
a[getid(i)=++m]=i;
if(1ll*i*i<M)s.push_back(i);
}
}
reverse(s.begin(),s.end());
for(int i:s){
a[getid(M/i)=++m]=M/i;
}
// for(int i=1;i<=m;i++)cerr<<a[i]<<"\n "[i<m];
for(int i=2;i<=m;i++){
for(int j=1;j<=m;j++){
if(a[j]%a[i]==0)d[j].push_back(i);
}
}
for(int i=1;i<=n;i++){
ll x;
// x=1;
scanf("%lld",&x);
if(M%x==0)t[getid(x)]++;
else ljx++;
}
dfs(m,m);
cout<<(ans<INF?ans:-1)<<endl;
cerr<<cnt<<endl;
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 6828kb
input:
2 5 6 1 2
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 1ms
memory: 6448kb
input:
3 6 5 1 2 3
output:
3
result:
ok single line: '3'
Test #3:
score: 0
Accepted
time: 44ms
memory: 7212kb
input:
2 114514 735134400 114 514
output:
20
result:
ok single line: '20'
Test #4:
score: 0
Accepted
time: 1ms
memory: 7168kb
input:
2 4 7 1 3
output:
-1
result:
ok single line: '-1'
Test #5:
score: 0
Accepted
time: 1ms
memory: 6348kb
input:
1 1 1 10000000000
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 213ms
memory: 8752kb
input:
74 8957165874 7351344000 9175800163 691239569 9932962027 8282987306 6063151113 3298305381 1841018684 8994004390 4000639989 9095647386 497768590 9210852932 3224414074 4123284054 8317046204 6543132098 4375640220 481970575 2636681880 7380029168 3311730585 9514203281 7961640038 8857267508 2357551453 179...
output:
1605821949
result:
ok single line: '1605821949'
Test #7:
score: 0
Accepted
time: 1ms
memory: 6344kb
input:
12 7840282002 8693528284 6716869047 8912311281 3532498787 9792923097 641489369 2061952840 5276308573 8674900429 3857207130 3435568680 1795487878 1741351693
output:
3493517872
result:
ok single line: '3493517872'
Test #8:
score: 0
Accepted
time: 212ms
memory: 9144kb
input:
3378 6425529388 7351344000 2165587998 2120562002 5252091350 9721880258 1692140896 2719544612 567917797 8634606531 1331901524 6936705303 8505583423 1315696968 2476200194 6191465712 2824480554 4307460133 9171973651 9497302453 1187876818 6468969139 3500352853 4730326578 1298030025 5193458000 1044688955...
output:
2749860766
result:
ok single line: '2749860766'
Test #9:
score: 0
Accepted
time: 1ms
memory: 6156kb
input:
2744 5308645516 9608623822 3851224184 4231440603 3561326330 9716880175 62728600 6493884657 4916910713 6006161964 1698265047 7148416217 2490266505 9843394709 8268913629 3252952468 1311964587 9340371669 8936566694 1039973271 5943892725 8015460363 9097425153 3025376586 2623576720 3757783176 9445752851 ...
output:
504336349
result:
ok single line: '504336349'
Test #10:
score: 0
Accepted
time: 213ms
memory: 9348kb
input:
88346 4782180530 7351344000 3667620194 7503711838 9239451336 4395875618 7173015664 7880070515 6337710353 822637860 225610001 7068873169 874115406 9881064263 6513040923 1739138083 6618265224 6758705336 7842045926 7475245109 8888489353 1020804103 7862164687 1456215420 9644923233 852743592 879560120 82...
output:
1106596876
result:
ok single line: '1106596876'
Test #11:
score: 0
Accepted
time: 3ms
memory: 6096kb
input:
24940 2255231250 7952282922 7824308611 778609102 8235321691 902787647 928287207 6558644508 7104942042 7459678953 2980176017 4961658600 9905890696 5029978542 9521618704 3901512946 4912952894 9420509352 2619542054 8740585806 3640951881 2377272196 6973057099 1372269794 1428086504 3592654341 854391849 8...
output:
929875699
result:
ok single line: '929875699'
Test #12:
score: 0
Accepted
time: 1ms
memory: 6096kb
input:
32 102024678 9708441014 4309108293 86 1 132315932 225777698 3893155157 2 1 1 4854220507 1 1 112888849 9708441014 43 1 3438238935 6803896303 225777698 1 1 332082234 1 1 1 9322240949 1 86 86 5257843768 86 2719257541
output:
-1
result:
ok single line: '-1'
Test #13:
score: 0
Accepted
time: 210ms
memory: 9372kb
input:
74 8957165874 7351344000 99000 95040 1 1 1 8353800 107712 1113840 4086112184 120120 56160 13127400 6984070338 23760 11220 4149178931 97240 1 3131308267 7344 2669167291 1 1 1 1 1 4347657073 15315300 2972501234 79560 7202650525 7837261625 11440 7936967053 11200 235620 8766964991 11440 1 2459605851 1 5...
output:
1605821905
result:
ok single line: '1605821905'
Test #14:
score: 0
Accepted
time: 215ms
memory: 8820kb
input:
3378 6425529388 7351344000 1512 40840800 3525919453 1 1 1 72072000 2691183741 15300 149600 8788596876 2660655926 4800 1 13464 27720 6340347401 9134068166 4500 1 240240 1 8938653050 1 65520 1 171360 10210200 1 10200 3959592729 1 95472 8975677637 26254800 1 138600 5018526731 1 1663200 336600 471240 32...
output:
2749858562
result:
ok single line: '2749858562'
Test #15:
score: 0
Accepted
time: 215ms
memory: 8784kb
input:
88346 4782180530 7351344000 1 4084080 336600 1 1 51000 1 7551145220 1 18018000 707200 78540 79560 7565163529 30630600 35700 1 7100752182 840 3674834085 2079000 720720 49008960 2033275878 1 6323141754 3360 3738287109 2639093537 277200 3020317639 95756755 9567316528 785400 2200 2042040 1 3014514354 50...
output:
1106537444
result:
ok single line: '1106537444'
Test #16:
score: 0
Accepted
time: 1ms
memory: 7212kb
input:
12 7840282002 8693528284 3065419 875834 1 1 1 1 1 6130838 1 1608721 709 9432610420
output:
3493517860
result:
ok single line: '3493517860'
Test #17:
score: 0
Accepted
time: 1ms
memory: 7460kb
input:
2744 5308645516 9608623822 62728600 4916910713 1698265047 40372369 686330273 1311964587 8936566694 17 1 1 238 7869276554 6828450901 119 7204528554 1 238 3077031002 80744738 7663982006 1 3017230010 9719561197 2896495632 354382836 1 4770395400 1 1 282606583 1 1 1 1 282606583 428714251 565213166 17 266...
output:
504334361
result:
ok single line: '504334361'
Test #18:
score: 0
Accepted
time: 3ms
memory: 6008kb
input:
24940 2255231250 7952282922 1 75021537 78887 1 5029978542 1 3976141461 159 3640951881 1 3 53 634 1 3976141461 298182317 1325380487 25086066 16801 1 9102259793 1 9523629136 1325380487 50014358 1 6599612694 6888745078 53 473322 1582390485 1 7179892343 100806 159 1 157774 7308607729 7661170199 74991630...
output:
929858405
result:
ok single line: '929858405'
Test #19:
score: 0
Accepted
time: 32ms
memory: 8120kb
input:
84 8597529626 918918000 1 15300 1 24024 1 26928 1 72 7351519877 1 1 1 23100 146367267 1 1 2898672885 1 589050 1 168300 1 5678365973 20420400 1 1901171356 556920 25740 1 7293000 2098074248 8190 1093446807 204 1 7243301202 5048501007 30888 1 6930 41580 923411734 2772 3443766953 165 7457269781 630 6426...
output:
7678611651
result:
ok single line: '7678611651'
Test #20:
score: 0
Accepted
time: 29ms
memory: 7008kb
input:
4946 8392096768 918918000 1 19500 1 1 462 1 1 1 1089317876 4950 244311183 8365355748 1 1 1 8086673571 3891753630 1 1 277200 1 8805186436 486200 1540 308816488 780 15708 1 5105100 248732566 4313429395 1 2702700 18564 8190 336600 1 22440 8121568960 8489326161 8835750 570326868 1 1 150 7208246886 1 1 5...
output:
7473180361
result:
ok single line: '7473180361'
Test #21:
score: 0
Accepted
time: 39ms
memory: 8020kb
input:
95558 6735809783 918918000 1 4950 3615834619 9168228593 9452281962 4590 5469750 8376770932 1 5037636549 1 1 1540 1 2466184602 400 1 1950 17325 154440 1 340340 1 17850 107100 1 4173300697 298350 1 23100 325819026 3543301285 1 971149619 1 1192494275 1170 685415618 1 8451140191 4352222654 7328238057 1 ...
output:
5816923704
result:
ok single line: '5816923704'
Test #22:
score: 0
Accepted
time: 0ms
memory: 6460kb
input:
75 1775613050 7439333297 9128964160 223 4016264282 2299234979 2662647190 1 11 1598364790 1 5974627342 3791 1471887073 11 17 9987487775 1 223 1 39782531 5294154284 1 1 1 5537425145 8958078974 437607841 1 1 5921589413 6141512946 676303027 2627784492 3226842559 1 39782531 5461124902 7623339541 87291381...
output:
1099310037
result:
ok single line: '1099310037'
Test #23:
score: 0
Accepted
time: 1ms
memory: 7800kb
input:
1232 7275212896 7774481184 22600236 1 1 1992 242952537 1 6 1 8386319056 1 1 1 1295746864 1 544584 2017758860 8814114653 4817932380 8136143955 672356407 5918157470 4204073582 1 1992 6879426079 1 11708556 3668091448 7533412 1 7845910555 1 22600236 971810148 1 745926388 3887240592 323936716 3631917073 ...
output:
3387972710
result:
ok single line: '3387972710'
Test #24:
score: 0
Accepted
time: 0ms
memory: 7760kb
input:
45624 5618925911 5045813387 2403913 1 1 691510997 1 1 1 8232623498 5045813387 2403913 1 1 1 2403913 441825807 1 3656270650 1 2403913 2099 1 1 5135012544 2403913 2099 1 1 2099 2016622988 743730399 1 1 1 6567161508 1 2403913 5045813387 1 1 1 1 9583887005 7858714512 6592405183 4646502928 5045813387 1 2...
output:
573120109
result:
ok single line: '573120109'
Test #25:
score: 0
Accepted
time: 1ms
memory: 7260kb
input:
679 286 6461786670 1 7828015603 29591 145 1 27732990 8078467464 5020724289 1716278 924433 8342562359 9814876143 218370 1 11049 1 1656172807 1122538652 7538225099 1165 6604344851 1 63754 7088692553 67570 111410115 1 5148834 502 8848721766 2510 753 1 16960070 2513289377 9992315163 3063445375 435 1 269...
output:
-1
result:
ok single line: '-1'
Test #26:
score: 0
Accepted
time: 0ms
memory: 7240kb
input:
38 9399057342 101080980 1 36465 6930 1 4636338922 1 9200432985 20790 23562 1 1 1580919505 765765 29172 2748105226 9438 1 1 4451002952 999030403 102102 858 1 3461248492 8805972060 1 1 28314 1 100980 172788 51051 1342119215 2329124781 518364 1 1 1
output:
9297976373
result:
ok single line: '9297976373'
Test #27:
score: 0
Accepted
time: 0ms
memory: 6328kb
input:
1603 9193624484 101080980 328185 417690 726124833 117810 297297 2566605835 1 1386 955334292 1326 962676 7189625666 756 363 6117085251 5444083697 7854 1 1 1 2620407373 8950825965 2720104258 13 6866863890 1 2447684857 476 2167405855 1 1 1 1896241091 1 1 121 4656019942 1989 1 1260 154 8793567341 707174...
output:
9092544004
result:
ok single line: '9092544004'
Test #28:
score: 0
Accepted
time: 10ms
memory: 7324kb
input:
94920 3242370203 101080980 1 1 330 1 9093508780 1 1076800521 9984705890 3388 494568437 7507109677 1169260988 1 70 1 19890 1 2406690 10010 90 2002 1 1 7615168690 4000512259 990990 5610 765 14 7632812362 5418944582 5979159241 38115 841140032 1110780 78 1 6930 3786715382 1 4209002616 459459 16830 37437...
output:
3141321160
result:
ok single line: '3141321160'
Test #29:
score: 0
Accepted
time: 1ms
memory: 6848kb
input:
64 8282173470 3621855807 2758168240 1 3416147106 3621855807 1 1 5756209356 2268570381 3 1 1 1 1 7968075164 4385234975 1 1 1 4162123409 2018972660 3621855807 1 1 1 1 3621855807 1 3 3843848464 6108467544 1 9699708245 1 3621855807 9 1207285269 9531199702 1 1207285269 9 402428423 402428423 1207285269 1 ...
output:
4660317674
result:
ok single line: '4660317674'
Test #30:
score: 0
Accepted
time: 1ms
memory: 7992kb
input:
513 2371707908 5400401407 323 17 8811654968 9085802782 10013 2025596583 589 5840496191 1 174206497 1 608919903 1 1 1 139526579 284231653 1 31 1 1 19 539339 6971648200 31 5400401407 539339 1 9500320877 1 1 5400401407 5400401407 5828480219 284231653 2258595301 539339 5003356937 9182274892 3325523750 1...
output:
2054037389
result:
ok single line: '2054037389'
Test #31:
score: 0
Accepted
time: 0ms
memory: 7784kb
input:
49904 6420453627 5666254455 5 5285303947 1 3 1 1 1 6939737469 1 4676095330 5591908030 5 5144580569 518282749 1 1 7718603279 5268109804 2749488733 5265886093 1 5 377750297 6157446831 3 5666254455 8742922099 1 3626738482 3894290480 1 5 377750297 5665585541 1 8892995365 6735747355 5 1 1 1 1 5 566625445...
output:
754211841
result:
ok single line: '754211841'
Test #32:
score: 0
Accepted
time: 5ms
memory: 7584kb
input:
54586 697 8529497259 4685675008 1 309 3174357 1 2843165753 309 1 309 30819 1 103 9211987715 1 2933227528 10273 3 318601173 4883663348 1058119 82810653 1 1 9040437984 384732208 868545170 5040071081 8095649132 1 1 82810653 8526795160 5293869690 1 1 3596931381 30819 393489706 8529497259 5521778806 3 78...
output:
-1
result:
ok single line: '-1'
Test #33:
score: 0
Accepted
time: 6ms
memory: 7180kb
input:
100000 10000000000 10000000000 9999999992 9999999990 9999999997 9999999993 9999999991 10000000000 9999999994 9999999992 9999999995 9999999996 9999999993 9999999998 9999999998 10000000000 9999999991 9999999994 9999999991 9999999991 9999999999 9999999998 9999999994 9999999995 9999999996 9999999992 999...
output:
99999
result:
ok single line: '99999'
Extra Test:
score: 0
Extra Test Passed