QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#612711#4788. Gravityucup-team4153#TL 3ms11736kbC++202.1kb2024-10-05 12:39:372024-10-05 12:39:39

Judging History

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

  • [2024-10-05 12:39:39]
  • 评测
  • 测评结果:TL
  • 用时:3ms
  • 内存:11736kb
  • [2024-10-05 12:39:37]
  • 提交

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*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;
}

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 11736kb

input:

10 10
..........
..######..
..#....#..
..#.#..#..
..#..#.#..
..#....#..
..######..
..........
..#....#..
.......#..


output:

..........
..........
..######..
..#....#..
..#....#..
..#....#..
..#.##.#..
..######..
.......#..
..#....#..

result:

ok 10 lines

Test #2:

score: -100
Time Limit Exceeded

input:

1583 1799
#..###..##..#.####.##.##.###..#.....##..#.#.#.#......#.....##..#.##...#.#....#..##.###...#...##.###.#.....#.##.###...#..##.#...###..#.###.#...###..#.......#...#....#.#..#...##........#.#..#..##.....###...#..#.####..####...#..##......#........#..#.##.##..#..#....##.##.##..#..##.....###....#...

output:


result: