QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#419119#1425. Divgrass8cow#WA 169ms19340kbC++171.4kb2024-05-23 18:00:152024-05-23 18:00:19

Judging History

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

  • [2024-05-23 18:00:19]
  • 评测
  • 测评结果:WA
  • 用时:169ms
  • 内存:19340kb
  • [2024-05-23 18:00:15]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int n,m;
#define fi first
#define se second
map<int,int>e;
int t[201000];
void ad(int x,int z){x%=m;t[e[x]+n]--,e[x]+=z,t[e[x]+n]++;}
vector<int>qb[200100];
#define pb push_back
void sol(){
    e.clear();
    scanf("%d%d",&n,&m);
    for(int i=0;i<=n*2;i++)t[i]=0,qb[i].clear();
    t[n]=m;
    int al=0;
    for(int i=1,x,z;i<=n;i++)scanf("%d%d",&z,&x),ad(x,-z),ad(x+1,z),al+=z;
    if(t[n]==m){puts("-1");return;}
    for(auto it:e)if(it.se)qb[it.se+n].pb(it.fi);
    int ans=(al%m==0);
    vector<int>X;
    for(int i=n;i>=2;i--){
        for(int x:qb[i+n])X.pb(x);for(int x:qb[-i+n])X.pb(x);
        vector<int>Y=X;
        vector<pair<int,int> >xg;
        while(!Y.empty()){
            int u=Y.back(),v=(u+1)%m;Y.pop_back();
            int lj;if(e[u]>=i)lj=e[u]/i;else lj=-((-e[u])/i);
            t[e[u]+n]--;
            e[u]-=lj*i;xg.pb({u,-lj*i});
            t[e[u]+n]++;
            t[e[v]+n]--;
            bool fk=(abs(e[v])<i);
            xg.pb({v,lj});
            e[v]+=lj;fk&=(abs(e[v])>=i);
            t[e[v]+n]++;
            if(fk)Y.pb(v);
        }
        reverse(xg.begin(),xg.end());
        if(t[n]==m||t[n-(i-1)]==m||t[n+(i+1)]==m)ans++;
        for(auto it:xg){
            int x=it.first;
            t[e[x]+n]--,e[x]-=it.second,t[e[x]+n]++;
        }
    }
    printf("%d\n",ans);
}
int main(){
    int T;scanf("%d",&T);while(T--)sol();
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 8524kb

input:

3
5 2
1 0
1 0
1 0
1 0
1 0
5 3
-1 2
-1 1
-1 0
1 1
-1 1
12 3
-1 0
-1 7
1 8
1 8
-1 4
-1 6
1 8
1 2
1 5
1 2
-1 9
1 5

output:

1
-1
2

result:

ok 3 number(s): "1 -1 2"

Test #2:

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

input:

1
1 1
1 0

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

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

input:

4
1 1000000000
1 0
1 1
1 1000000000
1 1000000000
-1 0
1 1
-1 1000000000

output:

0
-1
0
-1

result:

ok 4 number(s): "0 -1 0 -1"

Test #4:

score: 0
Accepted
time: 33ms
memory: 8528kb

input:

100000
1 1
-1 0
1 1
1 0
1 1
-1 1
1 1
1 1
1 1
-1 2
1 1
1 2
1 1
-1 3
1 1
1 3
1 1
-1 4
1 1
1 4
1 1
-1 5
1 1
1 5
1 1
-1 6
1 1
1 6
1 1
-1 7
1 1
1 7
1 1
-1 8
1 1
1 8
1 1
-1 9
1 1
1 9
1 1
-1 10
1 1
1 10
1 1
-1 11
1 1
1 11
1 1
-1 12
1 1
1 12
1 1
-1 13
1 1
1 13
1 1
-1 14
1 1
1 14
1 1
-1 15
1 1
1 15
1 1
-1 16...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 100000 numbers

Test #5:

score: 0
Accepted
time: 27ms
memory: 8484kb

input:

50000
2 1
-1 0
-1 0
2 1
-1 0
1 0
2 1
-1 0
-1 1
2 1
-1 0
1 1
2 1
-1 0
-1 2
2 1
-1 0
1 2
2 1
-1 0
-1 3
2 1
-1 0
1 3
2 1
-1 0
-1 4
2 1
-1 0
1 4
2 1
-1 0
-1 5
2 1
-1 0
1 5
2 1
-1 0
-1 6
2 1
-1 0
1 6
2 1
-1 0
-1 7
2 1
-1 0
1 7
2 1
-1 0
-1 8
2 1
-1 0
1 8
2 1
-1 0
-1 9
2 1
-1 0
1 9
2 1
-1 0
-1 10
2 1
-1 0
...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 50000 numbers

Test #6:

score: 0
Accepted
time: 38ms
memory: 8412kb

input:

100000
1 170035890
1 835589389
1 433027164
1 407537923
1 293860673
-1 788447900
1 838946623
1 450237482
1 629410117
1 476559978
1 171248763
1 671271287
1 468119514
1 346821429
1 112217885
-1 249186444
1 760504335
1 622839250
1 206432863
1 481956490
1 344167459
-1 251322298
1 603763257
-1 255443178
1...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 100000 numbers

Test #7:

score: 0
Accepted
time: 27ms
memory: 8808kb

input:

18185
6 462481634
-1 877399979
-1 444077256
1 863609811
1 737864979
-1 36285324
1 213052314
10 318224330
-1 392130699
-1 865648776
1 786577813
-1 47209814
-1 582014903
-1 552524598
1 931469640
-1 520667488
1 246701061
-1 583303124
6 255562733
-1 824922940
1 140907808
-1 659810174
1 755380312
1 78398...

output:

1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
1
0
0
1
0
0
1
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
1
1
0
0
0
0
0
0
0
0
0
1
1
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
1
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
0
0
0
0
1
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
1
0
1
0
0
1
0
0
0
1
0
...

result:

ok 18185 numbers

Test #8:

score: 0
Accepted
time: 34ms
memory: 8852kb

input:

1955
6 251705778
-1 306007602
1 338569924
1 913388465
-1 293228463
-1 357117659
-1 694618291
75 20088478
1 562896192
1 23789274
-1 419033091
1 347705574
1 640321092
-1 24823981
1 921096576
-1 107646445
-1 667736867
1 531502674
1 830022166
1 86700568
-1 138594043
1 358907049
-1 751689887
-1 1199423
1...

output:

0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 1955 numbers

Test #9:

score: 0
Accepted
time: 51ms
memory: 9528kb

input:

209
403 593744416
1 517964811
-1 181413985
-1 205129281
-1 814887706
1 968581352
1 714390388
1 635228328
-1 380906902
-1 696702331
1 6613143
1 15016617
1 431361558
1 672301213
1 135877994
1 455725955
-1 710803578
-1 530208577
1 95409526
-1 146277027
-1 504956437
-1 612977541
-1 12812223
-1 199941830...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 209 numbers

Test #10:

score: 0
Accepted
time: 74ms
memory: 10360kb

input:

24
2434 636377467
-1 770106795
1 828277555
-1 274146643
-1 441882590
-1 54415246
1 830277363
-1 331528200
-1 515652110
1 73968564
-1 377803597
-1 737019678
-1 132017335
-1 908297411
-1 856987154
-1 539087469
1 811351978
1 288732948
1 773226717
-1 738752886
1 836337764
1 332156441
-1 289537204
1 9911...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 24 numbers

Test #11:

score: 0
Accepted
time: 116ms
memory: 18996kb

input:

8
42 457808739
-1 789149347
-1 452572683
-1 456424609
-1 640853004
-1 542172406
1 451142377
1 368673199
1 694199351
-1 961486131
-1 630564272
-1 880483909
-1 665295814
-1 572092289
1 216494167
-1 129377090
1 87527349
1 423453639
-1 438434619
1 449628033
1 696689831
-1 277173
-1 321621424
1 139535963...

output:

0
0
0
0
0
0
0
0

result:

ok 8 numbers

Test #12:

score: 0
Accepted
time: 169ms
memory: 19340kb

input:

1
100000 148857431
-1 30521050
-1 219978148
-1 929551318
-1 972784058
1 374088376
-1 76864642
1 185632011
1 95546675
1 66312268
1 305990708
1 310692844
-1 176379563
-1 609502588
-1 404411675
1 53930302
1 84483869
1 655924365
1 565254030
-1 649315722
1 658395194
-1 706455090
1 134319869
-1 626974501
...

output:

0

result:

ok 1 number(s): "0"

Test #13:

score: -100
Wrong Answer
time: 60ms
memory: 8816kb

input:

18265
9 2
-1 442105658
-1 626353674
-1 135302128
-1 669485390
-1 519357584
-1 434878556
-1 383172206
-1 718977796
-1 306699064
6 2
-1 465453985
-1 260161269
-1 685533869
-1 574919497
-1 373616571
-1 331367241
1 2
1 958204698
8 2
1 599513965
1 163265175
1 482253857
1 483275687
1 269395687
1 862915777...

output:

1
2
0
3
1
1
1
1
2
1
1
0
1
1
0
2
3
1
3
2
1
1
1
0
0
1
1
1
1
1
1
1
1
2
1
0
3
3
1
2
1
1
1
2
3
1
2
1
0
1
1
3
2
3
1
2
1
1
3
1
0
1
2
3
1
1
1
1
1
1
1
1
2
3
3
1
1
1
1
2
1
3
3
2
2
1
3
3
3
1
1
1
2
3
1
2
1
3
1
1
3
3
3
1
3
3
1
1
3
0
1
0
1
3
2
2
1
3
1
3
2
1
1
1
1
3
1
1
1
2
3
1
1
2
1
2
1
1
2
3
1
1
1
2
2
0
1
1
3
2
...

result:

wrong answer 1st numbers differ - expected: '2', found: '1'