QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#709071#9527. A Brand New Geometric ProblemA_zjzjAC ✓215ms9372kbC++142.0kb2024-11-04 11:11:222024-11-06 13:25:59

Judging History

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

  • [2024-11-06 13:25:59]
  • 管理员手动重测本题所有提交记录
  • 测评结果:AC
  • 用时:215ms
  • 内存:9372kb
  • [2024-11-06 09:26:59]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:97
  • 用时:214ms
  • 内存:9500kb
  • [2024-11-06 09:23:59]
  • hack成功,自动添加数据
  • (/hack/1137)
  • [2024-11-04 16:58:10]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:219ms
  • 内存:9340kb
  • [2024-11-04 16:55:58]
  • hack成功,自动添加数据
  • (/hack/1106)
  • [2024-11-04 11:11:23]
  • 评测
  • 测评结果:100
  • 用时:217ms
  • 内存:9608kb
  • [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