QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#68318 | #4788. Gravity | A_zjzj | TL | 25ms | 98248kb | C++14 | 1.1kb | 2022-12-15 18:46:14 | 2022-12-15 18:46:16 |
Judging History
answer
#include<bits/stdc++.h>
#define id(x,y) ((x-1)*m+y)
using namespace std;using ll=long long;const int N=2e3+10,M=N*N;
int n,m,k,d[N][N],f[M];char a[N][N],b[N][N];vector<pair<int,int> >A[M];
void add(int u,int v,int w){A[u].push_back({v,w});}
void bfs(){
queue<int>q;for(int j=1;j<=m;j++)q.push(id(n+1,j));for(int u;!q.empty();q.pop()){
u=q.front();for(auto [v,w]:A[u])if(f[v]<f[u]+w)f[v]=f[u]+w,q.push(v);
}
}
int main(){
scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%s",a[i]+1);for(int j=1;j<=m;j++)d[n+1][j]=n+1;
for(int i=n;i>=1;i--)for(int j=1;j<=m;j++)if(a[i][j]=='#')d[i][j]=i;else d[i][j]=d[i+1][j];
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(a[i][j]=='#')add(id(d[i+1][j],j),id(i,j),1);
for(int i=1;i<=n;i++)for(int j=1;j<m;j++)if(a[i][j]=='#'&&a[i][j+1]=='#'){
add(id(i,j),id(i,j+1),0),add(id(i,j+1),id(i,j),0);
}bfs();for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)b[i][j]='.';
// for(int i=1;i<=n;i++,puts(""))for(int j=1;j<=m;j++)printf("%d ",f[id(i,j)]);
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(a[i][j]=='#')b[f[id(i,j)]][j]='#';
for(int i=n;i>=1;i--)printf("%s\n",b[i]+1);return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 25ms
memory: 98248kb
input:
10 10 .......... ..######.. ..#....#.. ..#.#..#.. ..#..#.#.. ..#....#.. ..######.. .......... ..#....#.. .......#..
output:
.......... .......... ..######.. ..#....#.. ..#....#.. ..#....#.. ..#.##.#.. ..######.. .......#.. ..#....#..
result:
ok 10 lines
Test #2:
score: -100
Time Limit Exceeded
input:
1583 1799 #..###..##..#.####.##.##.###..#.....##..#.#.#.#......#.....##..#.##...#.#....#..##.###...#...##.###.#.....#.##.###...#..##.#...###..#.###.#...###..#.......#...#....#.#..#...##........#.#..#..##.....###...#..#.####..####...#..##......#........#..#.##.##..#..#....##.##.##..#..##.....###....#...