QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#419119 | #1425. Div | grass8cow# | WA | 169ms | 19340kb | C++17 | 1.4kb | 2024-05-23 18:00:15 | 2024-05-23 18:00:19 |
Judging History
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'