QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #582893 | #11. 矩阵变换 | _114514_ | 100 ✓ | 261ms | 4508kb | C++17 | 783b | 2024-09-22 17:43:48 | 2024-09-22 17:43:48 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int N=205,M=405;
int T,n,m,a[N][M],pos[N][N],id[N][N],bk[N];
void aug(int i){
if(id[i][0]==n)exit(-1);
int x=id[i][++id[i][0]];
if(bk[x]){
int j=bk[x];bk[x]=0;
if(pos[x][i]>pos[x][j])swap(i,j);
bk[x]=i;aug(j);
}else bk[x]=i;
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
rep(i,1,n)rep(j,1,m){
scanf("%d",&a[i][j]);
if(a[i][j])pos[i][a[i][j]]=j;
}
rep(i,1,n){
iota(id[i],id[i]+n+1,0);
sort(id[i]+1,id[i]+n+1,[&](int x,int y){return pos[x][i]>pos[y][i];});
}
memset(bk,0,sizeof(bk));
rep(i,1,n)aug(i);
rep(i,1,n)printf("%d%c",bk[i]," \n"[i==n]);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 0ms
memory: 3892kb
input:
5 3 5 2 0 3 1 0 3 0 1 0 2 0 1 2 3 0 3 5 2 3 1 0 0 0 1 0 2 3 1 0 3 0 2 3 5 0 3 2 0 1 2 0 0 1 3 0 1 3 2 0 3 5 0 2 0 3 1 2 1 0 0 3 3 0 0 1 2 3 5 0 2 3 0 1 3 0 0 1 2 2 1 0 0 3
output:
1 2 3 1 3 2 1 3 2 1 3 2 1 2 3
result:
points 1.0
Test #2:
score: 10
Accepted
time: 0ms
memory: 3836kb
input:
7 4 7 2 0 1 3 0 0 4 3 0 2 1 4 0 0 0 3 4 0 0 1 2 0 4 3 0 0 2 1 4 7 2 1 0 0 4 3 0 4 3 0 2 0 0 1 3 4 0 0 1 2 0 0 2 0 1 3 0 4 4 7 2 0 0 1 3 0 4 0 4 3 2 1 0 0 0 2 1 0 4 0 3 4 1 0 0 2 3 0 4 7 0 2 0 4 3 0 1 1 3 2 0 0 0 4 2 1 0 3 0 4 0 3 4 0 1 0 0 2 4 7 4 1 0 0 0 3 2 0 3 4 0 0 2 1 2 0 3 4 0 1 0 0 2 0 0 1 4 ...
output:
3 4 2 1 3 1 2 4 4 1 3 2 3 2 4 1 3 2 1 4 1 2 3 4 2 3 4 1
result:
points 1.0
Test #3:
score: 10
Accepted
time: 0ms
memory: 3904kb
input:
6 5 50 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 5 0 0 3 0 0 0 0 0 0 0 2 0 0 0 0 0 4 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 5 0 0 0 0 0 0 0 3 0 2 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 2 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0...
output:
5 3 1 2 4 1 5 3 2 4 1 4 5 3 2 2 4 5 3 1 2 5 4 3 1 1 3 5 2 4
result:
points 1.0
Test #4:
score: 10
Accepted
time: 1ms
memory: 3904kb
input:
7 7 150 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 7 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 4 0 0 0 0 ...
output:
5 1 7 2 6 3 4 3 6 2 5 1 4 7 3 4 7 5 6 2 1 2 6 4 5 1 7 3 6 7 5 1 4 3 2 2 4 1 6 7 3 5 5 3 4 6 7 1 2
result:
points 1.0
Test #5:
score: 10
Accepted
time: 3ms
memory: 3976kb
input:
10 25 200 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 0 0 0 7 10 0 0 0 0 0 0 0 0 0 22 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 18 0 0 0 0 0 0 0 0 0 0 0 0 0 0 19 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 14 0 0 0 15 0 0 0 17 0 24 0 0 0 0 12 13 0 0 0 0 0 0 0 23 0 0 1 0 0 0 0 0 ...
output:
2 23 4 14 8 13 10 7 21 12 11 20 25 18 3 17 15 22 24 6 19 9 1 5 16 8 10 18 17 11 2 21 9 22 1 15 7 23 6 12 20 5 14 4 24 25 3 19 16 13 11 8 16 2 9 21 22 18 6 23 14 17 7 13 25 1 20 19 5 3 15 24 10 4 12 8 25 5 18 6 17 3 11 23 7 19 24 4 16 21 14 10 2 13 15 1 20 22 9 12 19 4 8 23 18 14 2 20 17 10 16 21 7 3...
result:
points 1.0
Test #6:
score: 10
Accepted
time: 22ms
memory: 4076kb
input:
20 80 250 0 14 0 0 0 0 0 53 0 16 5 0 0 0 0 0 31 49 0 0 0 6 33 18 30 57 0 0 0 0 79 51 0 0 19 0 29 21 0 24 0 0 0 0 0 43 0 28 0 0 12 0 0 71 0 0 0 50 45 0 0 47 0 0 0 35 58 0 0 0 0 0 1 0 0 39 0 0 41 0 55 25 0 0 0 0 54 4 0 27 0 0 9 0 0 80 0 0 0 0 0 10 74 0 75 0 0 0 69 0 0 0 0 0 20 0 0 0 0 0 0 0 0 15 0 63 ...
output:
59 24 68 12 78 61 14 29 45 57 47 15 79 32 35 76 38 75 58 11 21 28 22 23 1 46 40 43 16 53 71 56 54 3 65 44 20 27 60 49 37 26 10 25 7 55 19 34 77 62 6 70 17 33 50 9 36 41 80 52 18 39 42 69 73 66 51 64 48 4 31 13 30 67 8 72 74 63 2 5 7 32 79 19 72 49 43 14 35 10 70 29 59 74 47 23 52 68 22 27 18 12 53 2...
result:
points 1.0
Test #7:
score: 10
Accepted
time: 61ms
memory: 4276kb
input:
30 120 300 0 0 0 15 112 0 0 0 89 0 61 13 0 6 0 4 0 24 0 98 0 32 88 0 0 43 35 0 21 0 0 0 87 0 0 0 52 76 42 0 59 97 0 0 0 51 0 0 104 0 67 0 94 53 120 105 33 0 106 45 80 39 14 62 116 5 0 0 69 27 0 25 0 0 0 0 20 101 0 0 0 0 0 0 0 0 18 0 0 0 0 0 0 31 0 83 0 0 0 0 41 49 90 36 0 0 0 0 0 0 0 0 0 0 73 0 2 84...
output:
99 118 41 28 49 16 20 73 90 89 25 106 71 100 109 57 8 116 45 30 4 35 96 1 42 80 77 67 75 79 115 47 5 85 27 114 108 51 60 40 88 62 92 19 101 39 18 54 53 26 119 36 83 9 74 21 120 94 110 38 52 31 59 2 117 32 48 34 37 66 105 15 69 24 56 104 14 93 112 87 76 98 91 55 3 111 50 23 86 68 29 22 10 84 58 81 11...
result:
points 1.0
Test #8:
score: 10
Accepted
time: 143ms
memory: 4272kb
input:
40 160 360 60 0 0 0 132 0 2 0 128 126 0 0 89 0 0 61 156 0 0 154 0 134 0 73 100 0 21 0 117 0 0 0 0 0 15 125 0 0 0 0 115 108 0 0 0 80 0 40 0 5 92 0 0 0 87 0 0 0 0 63 0 0 109 0 114 112 113 129 0 0 0 0 28 157 20 91 138 0 0 98 88 136 67 110 0 0 0 0 29 0 0 10 106 0 0 96 0 0 11 152 23 0 0 54 37 0 38 0 0 12...
output:
33 64 113 147 67 116 44 138 96 151 22 142 28 68 30 58 105 48 26 76 18 13 2 126 109 144 87 38 73 115 75 4 51 62 153 152 63 135 100 71 3 40 74 160 19 146 29 17 81 50 54 86 145 159 112 136 55 143 123 95 65 27 106 60 41 102 21 103 25 7 121 10 88 53 94 52 36 99 24 134 70 6 148 12 34 69 98 132 139 119 120...
result:
points 1.0
Test #9:
score: 10
Accepted
time: 222ms
memory: 4484kb
input:
45 190 390 107 0 190 0 70 7 0 0 0 43 0 133 158 0 118 171 127 0 0 164 25 0 0 99 0 0 189 84 0 27 0 57 0 147 0 34 0 0 180 114 130 0 0 0 0 0 79 35 0 119 0 0 54 0 0 0 0 128 0 0 0 44 0 51 0 0 97 24 23 0 148 168 166 36 0 167 0 0 0 104 0 55 0 0 122 0 47 0 0 0 0 139 0 0 22 0 0 108 67 0 0 0 161 20 0 150 103 8...
output:
3 168 141 45 31 27 40 46 118 51 162 28 145 134 165 84 62 61 49 146 92 111 177 120 179 36 47 9 123 30 64 42 188 90 67 87 35 52 66 16 24 96 70 143 150 130 95 15 5 60 83 135 59 163 43 175 93 76 115 116 144 18 171 82 63 10 20 127 131 12 79 105 182 110 164 137 138 155 173 125 122 139 184 38 68 156 22 121...
result:
points 1.0
Test #10:
score: 10
Accepted
time: 261ms
memory: 4508kb
input:
49 199 399 89 167 78 0 112 139 0 0 17 179 0 35 113 0 0 0 0 0 5 0 138 0 0 76 147 58 0 43 0 38 0 0 0 0 0 0 48 86 178 81 19 157 118 0 0 123 0 151 68 125 61 198 74 0 0 99 124 0 0 0 49 0 155 145 132 85 0 0 0 166 0 189 0 120 0 0 41 4 127 0 0 88 0 0 0 25 134 154 0 44 0 91 136 102 33 0 0 0 51 143 0 181 0 0 ...
output:
152 147 97 68 111 181 155 135 47 165 160 198 2 127 192 89 174 91 73 126 187 57 82 22 117 176 173 96 49 190 178 116 100 162 113 199 123 27 53 29 188 151 189 128 52 166 186 109 70 184 104 79 45 168 139 80 159 36 119 81 6 172 46 21 118 62 85 112 55 169 105 41 17 1 114 161 171 90 31 196 122 88 191 4 144...
result:
points 1.0