QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#134760#5371. Matrixmasterhuang30 1ms3632kbC++232.3kb2023-08-04 21:17:042023-08-04 21:17:07

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-04 21:17:07]
  • 评测
  • 测评结果:30
  • 用时:1ms
  • 内存:3632kb
  • [2023-08-04 21:17:04]
  • 提交

answer

#include<bits/stdc++.h>
#define LL long long
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=205,M=5505;
int TOT,n,m,a[N][N],b[N],c[N],tot=1,head[N],_head[N],d[N],S,T,nx,ny,tt,as[N][N];
struct edge{int to,nex,w;}e[M<<1];
inline void add(int u,int v,int w)
{
	e[++tot]={v,head[u],w};head[u]=tot;
	e[++tot]={u,head[v],0};head[v]=tot;
}
inline bool bfs()
{
	queue<int>q;memset(d,0,sizeof(d));d[S]=1;q.push(S);
	while(!q.empty())
	{
		int t=q.front();q.pop();
		for(int i=head[t];i;i=e[i].nex)
		{
			int to=e[i].to;
			if(!d[to]&&e[i].w>0) d[to]=d[t]+1,q.push(to);
		}
	}return d[T];
}
int dfs(int x,int flow)
{
	if(x==T) return flow;int old=flow;
	for(int &i=_head[x];i;i=e[i].nex)
	{
		int to=e[i].to;
		if(d[to]==d[x]+1&&e[i].w>0)
		{
			int nw=dfs(to,min(e[i].w,flow));flow-=nw;
			e[i].w-=nw,e[i^1].w+=nw;
			if(!flow) break;
		}
	}return (flow==old)&&(d[x]=0),old-flow;
}
inline int dinic(){int ans=0;while(bfs()) memcpy(_head,head,sizeof(head)),ans+=dfs(S,1e9);return ans;}
inline bool chk()
{
//	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(nx==-1||a[i][j]<a[nx][ny]) nx=i,ny=j;
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(a[i][j]) return nx=i,ny=j,1;return 0; 
}
inline void sol()
{
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(a[i][j]<0) return cout<<"-1\n",void();
	for(int i=1,s=0;i<=n;i++,s=0){for(int j=1;j<=n;j++) s+=a[i][j];b[i]=s;}
	for(int i=1,s=0;i<=n;i++,s=0){for(int j=1;j<=n;j++) s+=a[j][i];b[i+n]=s;}
	for(int i=1;i<2*n;i++) if(b[i]^b[i+1]) return cout<<"-1\n",void();S=0;T=2*n+1;tt=0;
	while(chk())
	{
		tot=1;memset(head,0,sizeof(head));
		for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(a[i][j]) add(i,n+j,1);
		for(int i=1;i<=n;i++) add(S,i,1),add(i+n,T,1);int ans=dinic();assert(ans==n);
		for(int i=1;i<=n;i++) for(int j=head[i];j;j=e[j].nex) if(!e[j].w){c[i]=e[j].to-n;break;}
		int mn=1e9;for(int i=1;i<=n;i++) mn=min(mn,a[i][c[i]]);as[++tt][0]=mn;
		for(int i=1;i<=n;i++) a[i][c[i]]-=mn,as[tt][i]=c[i];
	}cout<<tt<<"\n";
	for(int i=1;i<=tt;i++,cout<<"\n") for(int j=0;j<=n;j++) cout<<as[i][j]<<" ";
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>TOT;
	while(TOT--){cin>>n;for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>a[i][j];sol();}
	return 0;
}

详细

Subtask #1:

score: 30
Accepted

Test #1:

score: 30
Accepted
time: 1ms
memory: 3568kb

input:

10
5
41 18467 6334 26500 2995
19169 15724 11478 29358 -21392
26962 24464 5705 28145 -30939
23281 16827 9961 491 3777
-15116 -21145 20859 -30157 99896
5
4827 5436 32391 14604 1869
3902 153 292 12382 42398
17421 18716 19718 19895 -16623
5447 21726 14771 11538 5645
27530 13096 -8045 708 25838
5
41879 4...

output:

-1
-1
17
8106 1 2 3 4 5 
23247 1 2 3 5 4 
10526 1 3 2 5 4 
10350 5 3 2 1 4 
5684 2 3 1 5 4 
2380 5 2 1 3 4 
6290 5 2 1 4 3 
29460 2 1 5 4 3 
2974 5 4 1 2 3 
16557 5 4 1 3 2 
15455 4 1 5 3 2 
27014 3 4 5 1 2 
7101 4 3 5 1 2 
3550 4 3 5 2 1 
7367 2 5 4 3 1 
6233 3 5 4 2 1 
10323 5 3 4 2 1 
-1
-1
-1
-1...

result:

ok good solution (10 test cases)

Test #2:

score: 0
Accepted
time: 0ms
memory: 3512kb

input:

10
5
59894 57729 53053 37667 58044
49556 41863 58059 44760 72149
49555 42862 54181 52697 67092
55846 40495 51765 66802 51479
51536 83438 49329 64461 17623
5
6224 11008 5844 32609 13458
14989 32702 3195 20485 -2228
3093 14343 30523 1587 19597
29314 9503 7448 25200 -2322
15523 1587 22133 -10738 40638
...

output:

17
17623 1 2 3 4 5 
24240 1 2 3 5 4 
12318 2 1 3 5 4 
14921 1 3 2 5 4 
12982 2 1 5 3 4 
24256 2 1 5 4 3 
8173 2 5 1 4 3 
3110 1 5 2 4 3 
13790 4 5 2 1 3 
13640 5 3 1 4 2 
27742 5 4 1 3 2 
17018 3 4 5 1 2 
12836 4 3 5 1 2 
12202 3 5 4 1 2 
11041 4 5 2 3 1 
23833 3 5 4 2 1 
16662 5 3 4 2 1 
-1
17
5281...

result:

ok good solution (10 test cases)

Test #3:

score: 0
Accepted
time: 1ms
memory: 3632kb

input:

10
5
10202 3625 26477 4414 17773
9314 25824 29334 25874 -27855
24372 20159 11833 28070 -21943
7487 28297 7518 8177 11012
11116 -15414 -12671 -4044 83504
5
80335 81240 95764 92557 91633
81674 87052 107785 86199 78819
83374 82671 109099 81197 85188
80115 80496 89595 108544 82779
116031 110070 39286 73...

output:

-1
17
80335 1 2 3 4 5 
6717 5 2 3 4 1 
21492 2 1 3 4 5 
1283 2 1 4 3 5 
555 2 1 3 5 4 
72477 5 3 2 1 4 
39286 2 1 4 5 3 
7638 5 3 4 1 2 
27670 4 3 1 5 2 
15268 3 1 4 5 2 
4801 5 4 1 3 2 
3790 4 1 5 3 2 
18624 2 4 5 3 1 
50903 4 5 1 3 2 
62774 3 4 5 2 1 
10194 4 5 2 3 1 
17722 3 5 4 2 1 
-1
-1
-1
17
...

result:

ok good solution (10 test cases)

Test #4:

score: 0
Accepted
time: 1ms
memory: 3500kb

input:

10
5
22335 24708 38072 45631 16687
27829 32738 19360 45510 21996
22430 32748 37233 30145 24877
38308 18739 18383 18259 53744
36531 38500 34385 7888 30129
5
44671 57452 39279 47542 49809
36827 56746 58358 41115 45707
57345 54779 56063 52429 18137
37825 52474 36230 66538 45686
62085 17302 48823 31129 ...

output:

17
18259 1 2 3 4 5 
4076 1 2 4 3 5 
10403 5 2 4 3 1 
3904 2 1 4 3 5 
6284 5 3 4 2 1 
3890 4 3 1 2 5 
7888 2 1 3 5 4 
5478 2 1 4 5 3 
10559 4 1 2 5 3 
19844 3 4 2 5 1 
7438 2 4 1 5 3 
2345 4 5 2 1 3 
2537 3 4 1 5 2 
8565 4 5 1 2 3 
15691 3 4 5 1 2 
9186 4 3 5 1 2 
11086 4 5 3 1 2 
17
44671 1 2 3 4 5 ...

result:

ok good solution (10 test cases)

Test #5:

score: 0
Accepted
time: 1ms
memory: 3564kb

input:

10
5
14423 3527 11600 26969 1588
14015 5565 28 21543 16956
25347 2088 2943 12637 15092
22409 26463 5049 4681 -495
-18087 20464 38487 -7723 24966
5
608 32060 21221 1758 18035
29954 20888 14146 690 8004
7949 12843 21430 25620 5840
748 27067 4536 20783 20548
34423 -19176 12349 24831 21255
5
64025 55878...

output:

-1
-1
17
53784 1 2 3 4 5 
10241 1 3 2 4 5 
5840 5 3 2 4 1 
10804 5 2 4 3 1 
37996 2 1 4 3 5 
52551 5 3 2 1 4 
131 4 3 2 5 1 
4843 3 1 2 5 4 
4538 3 5 1 2 4 
14995 2 1 4 5 3 
2887 2 4 1 5 3 
1564 3 4 1 5 2 
2230 4 1 5 2 3 
28141 3 4 5 2 1 
46657 4 5 1 2 3 
19607 3 4 5 1 2 
25451 4 5 1 3 2 
-1
-1
-1
1...

result:

ok good solution (10 test cases)

Test #6:

score: 0
Accepted
time: 0ms
memory: 3504kb

input:

10
5
18115 1679 17110 25898 28
23073 788 23977 18132 -3140
29956 28689 26113 10008 -31936
12941 15790 1723 21363 11013
-21255 15884 -6093 -12571 86865
5
127174 109596 107467 104281 105705
124370 103467 113729 125263 87394
128549 116691 134564 123221 51198
112072 118025 131046 104994 88086
62058 1064...

output:

-1
17
103467 1 2 3 4 5 
1527 2 1 3 4 5 
108069 2 1 4 3 5 
14774 5 1 4 3 2 
378 1 5 4 3 2 
7825 1 4 2 3 5 
952 1 4 3 2 5 
14552 1 5 3 2 4 
14066 4 5 3 2 1 
81912 5 3 2 1 4 
9019 5 4 2 1 3 
17935 3 4 2 5 1 
70151 3 4 1 5 2 
19381 3 4 5 2 1 
58398 4 5 1 2 3 
21141 4 3 5 1 2 
10676 4 3 5 2 1 
-1
-1
-1
1...

result:

ok good solution (10 test cases)

Test #7:

score: 0
Accepted
time: 1ms
memory: 3628kb

input:

10
5
18337 1278 12393 7636 25608
30714 28164 31591 19949 -45166
19135 2505 13337 10004 20271
16337 2623 28664 9970 7658
-19271 30682 -20733 17693 56881
5
118623 106427 108494 117715 101283
127994 107536 109218 123168 84626
127738 106914 105591 113982 98317
128516 118161 100285 131953 73627
49671 113...

output:

-1
17
105591 1 2 3 4 5 
13032 1 3 2 4 5 
13330 5 3 2 4 1 
1945 5 2 4 3 1 
76066 2 1 4 3 5 
65724 5 3 2 1 4 
30361 2 1 4 5 3 
5610 5 1 4 2 3 
14674 5 4 2 1 3 
154 4 1 2 5 3 
43112 3 4 1 5 2 
15803 4 1 5 2 3 
34396 3 4 5 2 1 
62352 4 5 1 2 3 
30986 3 4 5 1 2 
22274 4 5 1 3 2 
17132 4 3 5 1 2 
17
79455...

result:

ok good solution (10 test cases)

Test #8:

score: 0
Accepted
time: 1ms
memory: 3504kb

input:

10
5
32179 16595 20169 2327 25783
12042 31310 28182 11058 14461
7926 9487 1670 32528 45442
5651 2258 7213 9860 72071
39255 37403 39819 41280 -60704
5
58360 64228 60090 62746 84076
74052 61459 76336 59121 58532
70485 80483 66556 57499 54477
64875 78368 84232 74216 27809
61728 44962 42286 75918 104606...

output:

-1
17
58360 1 2 3 4 5 
3099 5 2 3 4 1 
5097 2 1 3 4 5 
7660 5 3 2 4 1 
41149 2 1 4 3 5 
64875 5 3 2 1 4 
3801 4 3 2 5 1 
4147 3 1 2 5 4 
6896 3 5 1 2 4 
16350 2 1 4 5 3 
1632 2 4 1 5 3 
8442 5 4 1 2 3 
1879 3 4 1 5 2 
7309 4 1 5 2 3 
47168 3 4 5 2 1 
8553 4 5 1 2 3 
43083 4 5 1 3 2 
-1
-1
-1
17
2210...

result:

ok good solution (10 test cases)

Test #9:

score: 0
Accepted
time: 1ms
memory: 3568kb

input:

10
5
27577 12750 14007 23729 29929
24081 2995 2678 24676 53562
27753 20899 11784 15565 31991
3093 13608 6172 11243 73876
25488 57740 73351 32779 -81366
5
10168 5055 11191 5973 15469
8922 6748 5651 10986 15549
2144 16446 31577 26517 -28828
14629 29916 5874 15791 -18354
11993 -10309 -6437 -11411 64020...

output:

-1
-1
17
33292 1 2 3 4 5 
248 5 2 3 4 1 
18463 5 2 4 3 1 
12516 2 1 4 3 5 
1093 2 1 3 5 4 
33697 5 3 2 1 4 
2794 2 3 1 5 4 
25393 2 1 4 5 3 
7097 2 4 1 5 3 
2918 5 4 1 2 3 
13093 4 1 5 2 3 
26090 3 4 5 2 1 
2169 2 4 5 1 3 
8147 3 4 5 1 2 
4777 2 4 5 3 1 
12573 4 5 1 3 2 
9295 4 3 5 1 2 
-1
-1
17
139...

result:

ok good solution (10 test cases)

Test #10:

score: 0
Accepted
time: 1ms
memory: 3620kb

input:

10
5
52175 34573 47184 34242 48829
39726 48464 56486 42655 29672
58676 54948 45757 42343 15279
45044 49757 42978 51268 27956
21382 29261 24598 46495 95267
5
115939 94609 88842 92104 98792
89855 95791 96911 101968 105761
111710 103031 92884 106351 76310
116598 114955 95676 118795 44262
56184 81900 11...

output:

17
45757 1 2 3 4 5 
5511 1 3 2 4 5 
907 1 2 4 3 5 
1800 5 2 4 3 1 
34573 2 1 4 3 5 
5063 5 1 4 3 2 
635 5 4 2 3 1 
8519 3 4 1 2 5 
41331 5 3 2 1 4 
7471 4 3 2 5 1 
2173 4 3 1 5 2 
5164 3 5 1 2 4 
18312 3 4 1 5 2 
90 4 1 5 2 3 
11476 3 4 5 2 1 
24508 4 5 1 2 3 
3713 3 4 5 1 2 
17
92884 1 2 3 4 5 
230...

result:

ok good solution (10 test cases)

Subtask #2:

score: 0
Dangerous Syscalls

Dependency #1:

100%
Accepted

Test #11:

score: 0
Dangerous Syscalls

input:

10
30
3303373 3309415 3289962 3309855 3312694 3291644 3309691 3294908 3296047 3312358 3320956 3313078 3317639 3306313 3317589 3316838 3308551 3311957 3312323 3293346 3313147 3293374 3301630 3308503 3311855 3315564 3317401 3290456 3301303 3309428
3308147 3304361 3303158 3313330 3307333 3299369 330747...

output:


result:


Subtask #3:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%