QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#612699 | #4788. Gravity | ucup-team4153# | RE | 5ms | 9632kb | C++20 | 2.1kb | 2024-10-05 12:37:21 | 2024-10-05 12:37:22 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=2e3+5;
int n,m;
char grid[N][N];
bool ot[N][N];
struct node{
int id,t;
bool operator < (const node &oth) const {
return t>oth.t;
}
};
priority_queue<node>que;
set<int>pos[N];
int fa[N];
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
void uni(int x,int y){
int fx=find(x),fy=find(y);
if(fx==fy)return;
fa[fx]=fy;
}
int dir[4][2]={0,1,0,-1,1,0,-1,0};
vector<array<int,2>>vec[N*N];
int id[N][N];
bool vis[N*N];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=n-1;i>=0;i--){
for(int j=0;j<m;j++){
cin>>grid[i][j];
}
}
for(int i=0;i<n*m;i++)fa[i]=i;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(grid[i][j]=='.')continue;
for(int op=0;op<4;op++){
int x=i+dir[op][0],y=j+dir[op][1];
if(x<0 || x>=n || y<0 || y>=m || grid[x][y]=='.')continue;
uni(i*m+j,x*m+y);
}
pos[j].insert(i);
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(grid[i][j]=='.')continue;
id[i][j]=find(i*m+j);
vec[id[i][j]].push_back({i,j});
que.push({id[i][j],i});
}
}
while(!que.empty()){
auto now=que.top();que.pop();
if(vis[now.id])continue;
vis[now.id]=true;
vector<array<int,2>>q;
for(auto u:vec[now.id]){
auto [x,y]=u;
pos[y].erase(x);
x-=now.t;
ot[x][y]=true;
q.push_back({x,y});
}
for(auto u:q){
auto [x,y]=u;
auto nxt= upper_bound(pos[y].begin(), pos[y].end(),x);
if(nxt==pos[y].end())continue;
int _id=id[*nxt][y];
que.push({_id,*nxt-x-1});
}
}
for(int i=n-1;i>=0;i--){
for(int j=0;j<m;j++){
// cout<<grid[i][j];
if(ot[i][j])cout<<'#';
else cout<<'.';
}cout<<'\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 5ms
memory: 9632kb
input:
10 10 .......... ..######.. ..#....#.. ..#.#..#.. ..#..#.#.. ..#....#.. ..######.. .......... ..#....#.. .......#..
output:
.......... .......... ..######.. ..#....#.. ..#....#.. ..#....#.. ..#.##.#.. ..######.. .......#.. ..#....#..
result:
ok 10 lines
Test #2:
score: -100
Runtime Error
input:
1583 1799 #..###..##..#.####.##.##.###..#.....##..#.#.#.#......#.....##..#.##...#.#....#..##.###...#...##.###.#.....#.##.###...#..##.#...###..#.###.#...###..#.......#...#....#.#..#...##........#.#..#..##.....###...#..#.####..####...#..##......#........#..#.##.##..#..#....##.##.##..#..##.....###....#...