NOI.AC
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #189393 | #3320. 矩形（square） | Crayon_ptwk | 100 | 1297ms | 3192kb | C++11 | 2.7kb | 2023-10-04 10:52:45 | 2023-10-04 13:00:58 |
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 510;
const int M = 2e5+20;
const int INF = 1e9+7;
int n,a[N][N],col[N],ans[N][N],cnt,k;
void add(int xi,int yi,int xj,int yj){
for(int i=xj;i<=xj;++i){
for(int j=yi;j<=yj;++j){
col[a[i][j]]++;
if(col[a[i][j]]==1)
cnt++;
}
}
for(int i=xi;i<xj;++i){
for(int j=yj;j<=yj;++j){
col[a[i][j]]++;
if(col[a[i][j]]==1)
cnt++;
}
}
}
void del(int xi,int yi,int xj,int yj){
for(int i=xj;i<=xj;++i){
for(int j=yi;j<=yj;++j){
col[a[i][j]]--;
if(col[a[i][j]]==0)
cnt--;
}
}
for(int i=xi;i<xj;++i){
for(int j=yj;j<=yj;++j){
col[a[i][j]]--;
if(col[a[i][j]]==0)
cnt--;
}
}
}
void rmv(int xi,int yi,int xj,int yj){
for(int i=xi;i<=xi;++i){
for(int j=yi;j<=yj;++j){
col[a[i][j]]--;
if(col[a[i][j]]==0)
cnt--;
}
}
for(int i=xi+1;i<=xj;++i){
for(int j=yi;j<=yi;++j){
col[a[i][j]]--;
if(col[a[i][j]]==0)
cnt--;
}
}
}
int main(){
cin>>n>>k;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
cin>>a[i][j];
// scanf("%d",&a[i][j]);
for(int j=n;j>=1;j--){
memset(col,0,sizeof(col));
cnt=0;
int xi=1,yi=j,lx=1,ly=j;
col[a[xi][yi]]++;
cnt=1;
while(xi<=n&&yi<=n){
while(lx+1<=n&&ly+1<=n){
add(xi,yi,lx+1,ly+1);
if(cnt>k){
del(xi,yi,lx+1,ly+1);
break;
}
lx++;ly++;
// cout<<"lx="<<lx<<" ly="<<ly<<endl;
// return 0;
}
ans[xi][yi]=lx-xi+1;
rmv(xi,yi,lx,ly);
xi++,yi++;
}
}
for(int i=2;i<=n;++i){
memset(col,0,sizeof(col));
cnt=0;
int xi=i,yi=1,lx=i,ly=1;
col[a[xi][yi]]++;
cnt=1;
while(xi<=n&&yi<=n){
while(lx+1<=n&&ly+1<=n){
add(xi,yi,lx+1,ly+1);
if(cnt>k){
del(xi,yi,lx+1,ly+1);
break;
}
lx++;ly++;
}
ans[xi][yi]=lx-xi+1;
rmv(xi,yi,lx,ly);
xi++,yi++;
}
}
for(int i=1;i<=n;++i,puts(""))
for(int j=1;j<=n;++j){
printf("%d ",ans[i][j]);
}
return 0;
}
Details
小提示：点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 1392kb
input:
50 12 8 1 9 3 12 10 2 3 5 3 8 6 2 3 11 6 7 3 2 8 10 3 7 11 2 1 10 4 10 5 9 8 5 4 11 5 2 5 11 10 7 5 ...
output:
12 11 10 9 8 7 6 5 4 4 5 5 5 12 12 12 12 12 12 12 12 12 12 12 18 18 17 16 15 14 13 12 11 10 10 10 10...
result:
ok 50 lines
Test #2:
score: 10
Accepted
time: 0ms
memory: 1392kb
input:
50 14 3 13 9 2 14 12 3 13 6 13 7 12 3 10 13 4 12 4 10 9 8 6 1 14 9 13 2 6 1 2 3 13 11 4 2 6 10 5 14 ...
output:
7 7 18 17 16 15 14 13 12 11 10 9 8 7 7 7 7 6 5 6 5 18 17 16 15 14 13 12 12 12 12 12 12 12 12 12 12 1...
result:
ok 50 lines
Test #3:
score: 10
Accepted
time: 0ms
memory: 1392kb
input:
50 17 17 8 14 12 2 7 17 3 11 5 8 15 11 4 3 15 13 12 6 5 9 3 9 8 7 13 3 7 7 13 16 6 10 17 16 7 6 5 3 ...
output:
19 19 19 19 19 19 19 18 17 16 15 14 13 12 11 10 9 8 7 6 6 6 8 8 8 7 12 12 12 11 10 9 8 7 6 7 9 9 9 8...
result:
ok 50 lines
Test #4:
score: 10
Accepted
time: 160ms
memory: 3192kb
input:
500 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
output:
17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 3 3 3 29 29 29 29 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15...
result:
ok 500 lines
Test #5:
score: 10
Accepted
time: 366ms
memory: 3188kb
input:
500 2 2 1 1 1 1 1 1 2 1 2 1 1 2 2 1 2 2 2 1 1 2 1 2 1 1 2 1 2 2 2 2 1 1 2 2 2 2 1 2 2 1 2 1 1 1 1 2 ...
output:
500 499 498 497 496 495 494 493 492 491 490 489 488 487 486 485 484 483 482 481 480 479 478 477 476 ...
result:
ok 500 lines
Test #6:
score: 10
Accepted
time: 142ms
memory: 3192kb
input:
500 2 2 1 2 1 1 1 1 2 1 1 1 1 1 2 2 1 1 1 2 2 1 2 2 1 2 1 1 1 2 1 2 2 2 1 1 2 2 2 1 1 1 2 1 2 1 1 2 ...
output:
13 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 47 47 47 47 47 47 47 47 47 46 45 44 43 42 41 4...
result:
ok 500 lines
Test #7:
score: 10
Accepted
time: 151ms
memory: 3192kb
input:
500 2 1 1 2 2 2 1 2 1 2 2 1 2 1 2 2 2 2 1 1 1 1 1 1 2 1 1 1 1 1 2 2 1 2 2 2 2 1 1 2 1 2 2 1 2 2 2 2 ...
output:
49 49 49 49 49 49 49 49 49 49 49 49 49 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 2...
result:
ok 500 lines
Test #8:
score: 10
Accepted
time: 146ms
memory: 3188kb
input:
500 162 11 100 62 113 44 157 79 78 156 9 78 50 149 145 54 72 138 145 5 55 51 129 37 114 95 3 63 5 21...
output:
29 29 29 28 28 27 26 28 28 29 29 29 29 29 29 28 27 26 25 24 24 24 25 26 26 25 25 25 27 26 25 25 29 2...
result:
ok 500 lines
Test #9:
score: 10
Accepted
time: 165ms
memory: 3192kb
input:
500 171 23 35 15 28 60 69 4 90 37 165 8 163 129 20 87 61 115 39 135 78 55 96 21 118 165 23 145 21 16...
output:
30 29 28 27 27 31 30 29 28 27 27 27 27 28 27 26 28 29 28 27 29 30 29 28 27 30 29 33 32 31 30 29 28 3...
result:
ok 500 lines
Test #10:
score: 10
Accepted
time: 167ms
memory: 3188kb
input:
500 168 141 99 128 16 72 106 42 137 15 57 113 3 17 116 13 91 147 104 55 125 32 46 85 51 103 15 156 7...
output:
28 28 28 28 31 31 31 31 31 30 29 28 27 27 27 27 29 29 29 29 29 30 29 29 29 29 29 29 29 29 29 29 28 2...
result:
ok 500 lines
Extra Test:
score: 0
Extra Test Passed
