結果

問題 No.2657 Falling Block Game
ユーザー amano_hina
提出日時 2024-03-01 22:45:13
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,725 bytes
コンパイル時間 1,788 ms
コンパイル使用メモリ 182,272 KB
実行使用メモリ 17,380 KB
最終ジャッジ日時 2024-09-29 14:37:41
合計ジャッジ時間 5,181 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13 WA * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
//#include<cstdio>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
//#define int long long
typedef long long ll;
#define F first
#define S second
#define pb emplace_back
string s[100005];
map<pair<int,int>,int> dp;
vector<int> v[100005];
int rea[100005],ans[100005];
int n,m;
bool vis[100005];
/*bool cmp(pair<pair<int,int>,int> p1,pair<pair<int,int>,int> p2)
{
    if(p1.F.F!=p2.F.S) return p1.F.F<p2.F.F;
    else
    {
        if(abs(p1.S)!=abs(p2.S)) return abs(p1.S)<abs(p2.S);
        else return p1.F.S<p2.F.S;
    }
}*/
void bfs(int x)
{
    priority_queue<pair<pair<int,pair<int,int>>,int>,vector<pair<pair<int,pair<int,int>>,int>>,greater<pair<pair<int,pair<int,int>>,int>>> pq;
    for(int i=0;i<=m;i++) vis[i]=0;
    for(int i=0;i<=m;i++)
    {
        for(auto j:v[i]) if(s[x][j]!='#')
        {
            //cout<<"?? "<<j<<'\n';
            pq.push(make_pair(make_pair(i,make_pair(0,0)),j));
        }
    }
    //cout<<x<<'\n';
    while(!pq.empty())
    {
        pair<pair<int,pair<int,int>>,int> p=pq.top();
        pq.pop();
        //cout<<"rtny ujunyt "<<p.F.F<<' '<<p.F.S<<' '<<p.S<<'\n';
        if(!vis[p.S])
        {
            //cout<<p.F.S<<' ';
            ans[p.S]=p.F.F;
            vis[p.S]=1;
            if(p.F.S.S==0)
            {
                if(p.S+1<m&&s[x][p.S+1]!='#') pq.push(make_pair(make_pair(max(p.F.F,1),make_pair(1,1)),p.S+1));
                if(p.S-1>=0&&s[x][p.S-1]!='#') pq.push(make_pair(make_pair(max(p.F.F,1),make_pair(1,-1)),p.S-1));
            }
            else if(p.F.S.S>0)
            {
                if(p.S+1<m&&s[x][p.S+1]!='#') pq.push(make_pair(make_pair(max(p.F.F,p.F.S.S+1),make_pair(p.F.S.S+1,p.F.S.S+1)),p.S+1));
            }
            else
            {
                if(p.S-1>=0&&s[x][p.S-1]!='#') pq.push(make_pair(make_pair(max(p.F.F,-p.F.S.S+1),make_pair(-p.F.S.S+1,p.F.S.S-1)),p.S-1));
            }
        }

    }
    //cout<<'\n';



}
signed main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>s[i];
    for(int i=0;i<m;i++) ans[i]=0;
    for(int i=0;i<m;i++) v[0].pb(i);
    for(int i=n-2;i>=0;i--)
    {
        //cout<<i<<endl;
        bfs(i);
        for(int j=0;j<=m;j++) v[j].clear();
        for(int j=0;j<m;j++) if(s[i][j]!='#')
        {
            //cout<<"? "<<j<<'\n';
            v[ans[j]].pb(j);
        }
        /*for(int i=0;i<m;i++) cout<<ans[i]<<' ';
        cout<<'\n';*/
    }
    for(int i=0;i<m;i++) cout<<ans[i]<<'\n';










}
0