結果

問題 No.2657 Falling Block Game
ユーザー amano_hinaamano_hina
提出日時 2024-03-01 22:52:37
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,777 bytes
コンパイル時間 1,744 ms
コンパイル使用メモリ 179,684 KB
実行使用メモリ 17,384 KB
最終ジャッジ日時 2024-09-29 14:41:26
合計ジャッジ時間 4,756 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
9,516 KB
testcase_01 AC 3 ms
9,160 KB
testcase_02 AC 3 ms
9,144 KB
testcase_03 AC 3 ms
8,944 KB
testcase_04 AC 11 ms
8,900 KB
testcase_05 WA -
testcase_06 AC 68 ms
14,456 KB
testcase_07 AC 181 ms
17,384 KB
testcase_08 AC 155 ms
9,408 KB
testcase_09 AC 60 ms
8,904 KB
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 AC 21 ms
10,908 KB
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 AC 53 ms
9,420 KB
testcase_31 AC 53 ms
9,028 KB
testcase_32 AC 52 ms
9,028 KB
testcase_33 AC 53 ms
9,160 KB
testcase_34 AC 52 ms
9,024 KB
testcase_35 AC 52 ms
9,000 KB
testcase_36 AC 54 ms
9,000 KB
testcase_37 AC 53 ms
8,960 KB
testcase_38 AC 53 ms
8,896 KB
testcase_39 AC 53 ms
8,872 KB
権限があれば一括ダウンロードができます

ソースコード

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];
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;
        for(int j=0;j<=m;j++) ans[j]=-1;
        bfs(i);
        for(int j=0;j<=m;j++) v[j].clear();
        for(int j=0;j<m;j++) if(ans[j]>=0)
        {
            //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';










}
/*
5 5
.....
#.#..
..##.
##...
.....
*/
0