QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#827940 | #6140. 矩阵游戏 | hamsterball# | 100 ✓ | 453ms | 5836kb | C++14 | 2.0kb | 2024-12-23 11:38:57 | 2024-12-23 11:39:02 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=303;
const int MAXV=1e6;
const ll MAX=0x3f3f3f3f3f3f3f3f;
const int MAX_I=0x3f3f3f3f;
int n,m,b[MAXN][MAXN],g[MAXN<<1][MAXN<<1],cnt[MAXN<<1];
ll dis[MAXN<<1];
queue<int> q;
bitset<MAXN<<1> vis;
bool spfa()
{
fill_n(dis,n+m+1,MAX);
dis[0]=cnt[0]=0;
vis.reset(),vis.set(0);
while(!q.empty()) q.pop();
q.push(0);
while(!q.empty())
{
int u=q.front();
q.pop(),vis.reset(u);
for(int v=0;v<=n+m;v++)
if(dis[v]>dis[u]+g[u][v])
{
dis[v]=dis[u]+g[u][v],cnt[v]=cnt[u]+1;
if(cnt[v]>=n+m+1) return 0;
if(!vis[v]) q.push(v),vis.set(v);
}
}
return 1;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++)
for(int j=1;j<m;j++)
scanf("%d",&b[i][j]);
for(int i=1;i<=n+1;i++) b[i][m]=b[i][m+1]=0;
for(int i=1;i<=m+1;i++) b[n][i]=b[n+1][i]=0;
for(int i=n;i>=1;i--)
for(int j=m;j>=1;j--)
b[i][j]-=b[i+1][j+1]+b[i+1][j]+b[i][j+1];
// memset(g,0x3f,sizeof(g));
for(int i=0;i<=n+m;i++)
fill_n(g[i],n+m+1,MAX_I);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if((i+j)&1) g[j+n][i]=MAXV-b[i][j],g[i][j+n]=b[i][j];
else g[i][j+n]=MAXV-b[i][j],g[j+n][i]=b[i][j];
}
for(int i=1;i<=n+m;i++)
g[0][i]=0;
if(!spfa())
{
printf("NO\n");
continue;
}
printf("YES\n");
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if((i+j)&1) b[i][j]+=dis[i]-dis[j+n];
else b[i][j]+=dis[j+n]-dis[i];
printf("%d%c",b[i][j]," \n"[j==m]);
}
}
return 0;
}
详细
Pretests
Final Tests
Test #1:
score: 5
Accepted
time: 0ms
memory: 4056kb
input:
10 3 3 9 21 22 16 3 3 28 30 13 4 3 3 17 10 5 30 3 3 30 27 30 25 3 3 22 19 28 12 3 3 30 27 21 28 3 3 4 25 11 5 3 3 12 24 24 30 3 3 5 4 27 8 3 3 20 29 17 18
output:
YES 0 0 18 6 3 0 0 13 0 YES 0 15 11 9 4 0 0 0 0 YES 7 5 0 0 5 0 0 0 25 YES 0 0 2 5 25 0 0 0 0 YES 0 0 13 16 6 0 0 6 0 YES 3 6 0 0 21 0 0 0 7 YES 0 0 25 4 0 0 2 5 0 YES 0 0 12 0 12 0 0 12 6 YES 0 0 4 5 0 0 14 8 0 YES 0 3 9 0 17 0 0 0 1
result:
ok you are right!!
Test #2:
score: 5
Accepted
time: 0ms
memory: 3892kb
input:
10 3 3 5 18 16 21 3 3 28 30 27 5 3 3 30 12 9 11 3 3 28 20 30 13 3 3 22 27 28 5 3 3 30 29 30 23 3 3 17 13 22 13 3 3 29 24 29 25 3 3 23 12 3 2 3 3 20 30 23 30
output:
YES 0 0 13 0 5 0 0 11 5 YES 0 1 24 22 5 0 0 0 0 YES 18 3 0 0 9 0 0 0 2 YES 0 0 9 17 11 0 0 2 0 YES 0 0 27 22 0 0 1 5 0 YES 0 0 6 7 23 0 0 0 0 YES 0 0 5 9 8 0 0 5 0 YES 1 0 0 4 24 0 0 1 0 YES 10 10 0 1 2 0 0 0 0 YES 0 0 10 0 20 0 0 3 7
result:
ok you are right!!
Test #3:
score: 5
Accepted
time: 0ms
memory: 3824kb
input:
10 3 3 17 22 17 27 3 3 30 24 30 30 3 3 11 16 10 15 3 3 29 18 19 27 3 3 12 2 25 26 3 3 27 28 29 30 3 3 14 11 8 16 3 3 29 27 26 15 3 3 1 21 25 12 3 3 30 28 21 27
output:
YES 0 0 5 0 17 0 0 0 10 YES 6 0 0 0 24 0 0 6 0 YES 0 1 5 0 10 0 0 0 5 YES 11 0 0 0 18 0 0 1 8 YES 10 0 0 0 2 0 0 23 1 YES 0 0 1 0 27 0 0 2 1 YES 3 3 0 0 8 0 0 0 8 YES 0 3 9 11 15 0 0 0 0 YES 0 0 21 1 0 0 12 12 0 YES 2 7 0 0 21 0 0 0 6
result:
ok you are right!!
Test #4:
score: 5
Accepted
time: 0ms
memory: 3892kb
input:
10 3 3 6 30 30 11 3 3 29 28 11 25 3 3 26 26 15 22 3 3 23 30 29 6 3 3 16 8 13 20 3 3 26 30 29 28 3 3 3 24 4 2 3 3 29 30 24 29 3 3 15 12 7 4 3 3 30 26 25 30
output:
YES 0 0 30 6 0 0 13 11 0 YES 1 17 0 0 11 0 0 0 14 YES 0 11 0 0 15 0 0 0 7 YES 0 0 30 23 0 0 0 6 0 YES 8 0 0 0 8 0 0 5 7 YES 0 0 5 1 25 0 0 3 0 YES 0 0 23 2 1 0 0 1 0 YES 0 5 1 0 24 0 0 0 5 YES 0 8 0 3 4 0 0 0 0 YES 4 1 0 0 25 0 0 0 5
result:
ok you are right!!
Test #5:
score: 5
Accepted
time: 0ms
memory: 3844kb
input:
10 10 2 240 8788 3257 6676 9748 4941 1268 2569 7827 10 2 9542 9328 8351 9362 9771 9183 8527 8640 7370 10 2 3144 7704 2054 9901 3567 120 2273 2407 4202 10 2 7337 9013 9119 9547 8526 8071 8475 6682 9273 10 2 746 9791 1891 3204 8908 1495 1353 9406 1176 10 2 9884 6039 4691 9956 8516 9454 9649 8966 9380 ...
output:
NO YES 7048 0 2494 0 6834 0 1517 0 7845 0 1926 0 7257 0 1270 0 7370 0 0 0 NO YES 6422 0 915 0 8098 0 1021 0 8526 0 0 0 8071 0 404 0 6278 0 2995 0 NO YES 7096 0 2788 0 3251 0 1440 0 8516 0 0 0 9454 0 195 0 8771 0 609 0 NO YES 8958 0 0 0 8441 0 1184 0 7886 0 1159 0 6749 0 2681 0 6695 0 2352 0 NO YES 8...
result:
ok you are right!!
Test #6:
score: 5
Accepted
time: 0ms
memory: 3816kb
input:
10 10 2 7221 6762 7271 4154 1804 3226 6434 8357 2359 10 2 8581 5933 9174 9731 9716 9180 8744 9947 6264 10 2 282 9689 7228 960 2522 6806 7516 7002 9829 10 2 9202 8816 8250 9267 8287 8105 9707 8985 9226 10 2 2004 254 7197 7613 9790 5556 3064 6363 6489 10 2 7863 9827 9600 9998 7626 6038 9530 8772 8501 ...
output:
NO YES 7688 0 893 0 5040 0 4134 0 5597 0 4119 0 5061 0 3683 0 6264 0 0 0 NO YES 7656 0 1546 0 7270 0 980 0 8287 0 0 0 8105 0 1602 0 7383 0 1843 0 NO YES 5264 0 2599 0 7228 0 2372 0 7626 0 0 0 6038 0 3492 0 5280 0 3221 0 NO YES 6291 0 1856 0 7172 0 0 0 9481 0 283 0 9133 0 711 0 4441 0 3348 0 YES 2586...
result:
ok you are right!!
Test #7:
score: 5
Accepted
time: 0ms
memory: 3912kb
input:
10 10 2 2492 6642 8650 4949 7971 7552 5729 6137 3224 10 2 8862 4232 4370 9422 9787 8443 9745 9230 9708 10 2 1073 3311 5736 6108 1985 2880 2596 1260 4678 10 2 9862 9822 8867 4686 9645 7259 7954 9855 9482 10 2 6532 3248 1799 3767 7693 4389 5786 1124 9586 10 2 7667 9393 6828 8642 9482 8512 8366 7067 87...
output:
YES 2492 0 0 0 6642 0 2008 0 2941 0 5030 0 2522 0 3207 0 2930 0 294 0 YES 8862 0 0 0 4232 0 138 0 9284 0 503 0 7940 0 1805 0 7425 0 2283 0 NO YES 8907 0 955 0 8867 0 0 0 4686 0 4959 0 2300 0 5654 0 4201 0 5281 0 NO YES 5102 0 2565 0 6828 0 0 0 8642 0 840 0 7672 0 694 0 6373 0 2404 0 NO YES 5629 0 18...
result:
ok you are right!!
Test #8:
score: 5
Accepted
time: 2ms
memory: 4240kb
input:
10 100 2 407406 741582 966880 693984 175204 991130 183615 326373 131306 366816 697972 180227 398068 835836 746523 999640 178807 545159 437329 536071 721606 306737 181599 455551 733444 231865 77996 588988 897019 804401 528918 524503 349494 623245 534144 344637 25518 791164 100668 547254 630911 346372...
output:
NO YES 647283 0 102846 0 747501 0 134576 0 781948 0 212413 0 766133 0 184288 0 659865 0 16206 0 593438 0 0 0 421730 0 265080 0 276696 0 666339 0 318563 0 458439 0 196118 0 666359 0 239005 0 357928 0 466265 0 451156 0 131492 0 861478 0 137602 0 458038 0 462088 0 399664 0 251663 0 706713 0 156922 0 83...
result:
ok you are right!!
Test #9:
score: 5
Accepted
time: 2ms
memory: 4148kb
input:
10 100 2 514849 121431 445450 996530 912655 547635 39581 89505 975458 843069 273144 700881 59053 289340 848708 32178 700710 194859 273472 213196 384827 341987 482545 308239 413944 599935 848280 843825 979288 195213 209986 440149 934390 768000 882462 200861 119570 174661 871708 511415 426500 576587 5...
output:
NO YES 695456 0 298080 0 498364 0 500209 0 361888 0 433407 0 479661 0 497781 0 238111 0 761888 0 170139 0 762822 0 181915 0 722759 0 184148 0 741213 0 156111 0 839902 0 110472 0 742142 0 243932 0 498709 0 439158 0 244278 0 640848 0 234542 0 349106 0 649644 0 79504 0 536258 0 426135 0 569778 0 378411...
result:
ok you are right!!
Test #10:
score: 5
Accepted
time: 0ms
memory: 4436kb
input:
10 100 2 650385 567657 465159 181316 696069 211308 655715 128129 988551 838473 44280 61031 528962 277047 286263 142130 248066 307713 578918 695526 89569 48119 569157 673222 295474 923221 90394 912892 523136 369133 635906 272262 887296 438346 625250 217263 729637 256075 898161 999382 845113 626531 74...
output:
NO YES 997572 0 0 0 831313 0 140282 0 842484 0 130157 0 481725 0 160423 0 809914 0 126258 0 313950 0 227108 0 721150 0 198312 0 629558 0 323356 0 319434 0 635666 0 333253 0 202906 0 133199 0 607576 0 229778 0 728527 0 202508 0 457123 0 399237 0 337800 0 313915 0 534342 0 206225 0 664500 0 173840 0 6...
result:
ok you are right!!
Test #11:
score: 5
Accepted
time: 417ms
memory: 5656kb
input:
10 300 298 0 0 1 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 0 0 0 0 1 0 1 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 1 0 0 1 0 0 0 1 0 1 1 1 1 0 1 1 0 1 1 0 0 1 1 0 0 1 1 0 1 1 0 0 0 0 1 1 0 0 0 0 0 1 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 1 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 1 1 0 1 1 1 0 0 0...
output:
NO YES 1 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 1 0 1 0 1 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 1 0 0 0 1 0 1 0 1 0 0 1 0 0 0 1 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 0 1 0 0...
result:
ok you are right!!
Test #12:
score: 5
Accepted
time: 410ms
memory: 5540kb
input:
10 297 296 0 0 1 0 1 0 1 0 1 1 0 1 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 1 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 1 1 0 1 1 1 0 0 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 1 1 0 1 1 1 1 1 1 1 0 0 0 1 1 0 1 1 1 1 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 1 0 1 0 0 1 1 0 0...
output:
NO YES 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 1 0 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 0 1 0 0 1 0 0 0 0 1 0 1 0 1 0 0 0 0 1 0 0 1 0 1 0 0 0...
result:
ok you are right!!
Test #13:
score: 5
Accepted
time: 418ms
memory: 5552kb
input:
10 297 299 1 0 1 0 0 0 1 0 1 0 1 1 0 1 0 1 0 0 1 0 1 1 0 1 0 1 0 1 1 0 0 0 0 0 0 1 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 1 1 1 0 0 1 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1 0 0 0 1 1 1 0 0 1 0 1 1 1 0 0 1 1 0 1 0 0 0 1 1 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 1 1 1 1 0 0 0 0 1 1 1 0 0 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 1...
output:
NO YES 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 0 0 1 0 0 1 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 1 0 0 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0...
result:
ok you are right!!
Test #14:
score: 5
Accepted
time: 423ms
memory: 5488kb
input:
10 298 299 0 1 0 1 1 1 1 1 1 0 0 1 0 0 1 0 1 1 1 0 1 1 1 0 1 1 0 0 0 1 0 0 0 0 1 1 0 1 1 0 0 0 1 1 0 1 0 1 0 0 1 0 1 1 0 1 1 0 1 0 1 1 1 0 0 0 0 0 1 1 1 0 1 0 1 1 1 0 0 0 1 0 0 1 0 0 1 1 0 1 0 1 0 0 0 0 1 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 1 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 1 0 1 1 0 0 1 1 0...
output:
NO YES 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 0 1 0 0 1 0 0 0 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 0 0 0 1 0 1 0 1 0 1 0 0 1 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0...
result:
ok you are right!!
Test #15:
score: 5
Accepted
time: 411ms
memory: 5548kb
input:
10 298 296 0 1 1 1 1 0 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0 1 0 0 1 0 1 0 1 0 1 1 1 1 1 0 1 0 0 1 0 1 0 1 0 0 0 1 0 1 1 1 0 0 0 1 1 0 1 1 0 1 1 0 1 0 0 1 1 1 0 0 0 1 1 1 0 0 1 0 1 0 1 1 0 0 1 1 0 1 0 0 1 0 0 1 1 0 0 0 1 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 1 0 1 1 1 1 0 0 1 0 1 0 0 1 1 1 1 0 1...
output:
NO YES 1 0 0 1 0 1 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 1 0 1 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 1 0 0 0 1 0 1 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 1 0 0 0 1 0 0 0 0 1 0 1 0 1 0 0 0 0 1 0 0 0 1 0 1 0 0 1 0 0 1 0 1 0 1 0 0 1 0 0...
result:
ok you are right!!
Test #16:
score: 5
Accepted
time: 438ms
memory: 5836kb
input:
10 295 299 3600561 469227 1519243 508870 2714139 2548515 3416122 1633507 1829918 1551817 3098121 1670950 2106466 1946727 1581396 3426393 1988045 2888135 2146489 1534631 2721599 3729764 456043 293501 882439 3099151 2941143 3610816 549774 1066237 3189705 2413286 2316602 3976215 3845403 862960 241887 2...
output:
NO YES 65194 343587 919518 354548 207891 287786 729382 756090 986382 502532 86206 402893 332155 282571 28979 292167 694679 562204 671128 170952 783835 315107 836152 951817 718989 552585 347429 330352 479925 3934 65484 807170 682575 220680 895716 904953 712472 253825 579764 210910 677602 440110 90113...
result:
ok you are right!!
Test #17:
score: 5
Accepted
time: 453ms
memory: 5576kb
input:
10 298 297 1203979 2459461 1123626 2165742 593951 2361185 60882 1597698 966249 1407808 2665213 1585110 1730464 732707 2642476 54357 96750 3459440 500455 1509802 2084769 1885656 824649 1394960 3065480 1964072 626742 582644 617926 652074 1646286 250370 1154127 1955950 327344 753408 2005921 2832519 933...
output:
NO YES 515156 945436 190645 62539 384403 562283 442612 586641 526340 279164 151388 569336 562496 33137 712756 621011 982543 736276 316749 279031 321029 663944 219531 425406 223773 457730 248787 40782 522412 390646 864024 355828 834351 764274 798472 245227 23148 766204 149703 505110 737395 986794 234...
result:
ok you are right!!
Test #18:
score: 5
Accepted
time: 431ms
memory: 5824kb
input:
10 296 296 2917992 3146628 3606537 755096 2325656 3902232 2435726 2851482 3134088 1183312 3680091 2970485 3974463 2456731 3306154 400789 1137399 1266637 1849976 2126197 1039996 2867787 711979 2828033 1651264 3781772 1152035 2861694 2479767 1853717 886722 2972156 4583 903432 3364054 3947134 3871761 3...
output:
NO YES 923837 345763 538650 225512 0 855256 549910 111744 501067 714260 688558 707313 528245 417986 220685 418853 130043 369023 270452 371958 710478 540567 105482 349498 923413 775599 394839 119959 534340 226247 309295 576270 170818 11451 522428 98958 841371 198006 907283 202616 833032 949902 87812 ...
result:
ok you are right!!
Test #19:
score: 5
Accepted
time: 428ms
memory: 5544kb
input:
10 297 297 13391 712464 2974864 1439202 1447544 1413180 800048 597109 3349875 2034207 1467293 796338 2354278 171222 1066675 2532591 208592 123178 2912280 3309432 3409173 1029236 2315777 2135394 3355241 69077 3113692 2937527 2948148 1151724 1640840 870814 42569 2304251 726055 3017332 2049772 2646010 ...
output:
NO YES 327434 190777 476700 784829 794131 828816 763092 12837 783154 856016 85055 721296 187996 716065 249200 189247 957632 955542 315265 70852 889007 281642 518093 91410 632079 348819 5247 454469 869316 357340 939132 333594 312923 735781 19170 472066 553420 360551 118381 657241 804189 805915 517446...
result:
ok you are right!!
Test #20:
score: 5
Accepted
time: 429ms
memory: 5568kb
input:
10 297 295 2251173 2102586 854138 210476 3746962 1050335 357886 1246625 2048656 3914401 2622120 2500826 3210040 3638713 646704 3538951 2675262 2202513 1600647 2451535 120429 782584 3574033 3344068 580591 2179489 3256587 684504 1805546 599720 3155847 2286982 2960267 502472 3365334 1420188 2393737 228...
output:
NO YES 315830 824571 413275 585425 166851 808113 972449 0 529912 955762 929838 552224 588480 782446 373526 210467 498247 752420 494431 87110 833865 571528 160623 976048 731131 1000000 801953 339533 407441 760038 669125 608882 487856 545987 277456 0 623400 106642 398736 343956 354992 676571 279314 90...
result:
ok you are right!!
Extra Test:
score: 0
Extra Test Passed