Submission #932669

#	Time	Username	Problem	Language	Result	Execution time	Memory
932669		Whisper	Patkice II (COCI21_patkice2)	C++17	110 / 110	175 ms	109536 KiB

Main

#include "bits/stdc++.h"
#pragma GCC optimize("Ofast")
using namespace std; 

#define ii pair< ll , ll >
#define pb push_back
#define fi first
#define se second
using ll = long long;

constexpr ll LINF = ( 1e18 + 5 );
constexpr ll MAX = 1e6 + 5;
constexpr ll INF = ( 1e9 + 5 );
constexpr int MOD = 1e9 + 7;

template<class X  , class Y>
    bool maximize( X& x , const Y& y ){
        if ( x < y ){
            x = y;
            return true;
        }
        return false;
    }
template<class X , class Y>
    bool minimize( X& x , const Y& y ){
        if ( x > y ){
            x = y;
            return true;
        }
        return false;
    }
template<class T> using MaxHeap = priority_queue< T , vector<T> , less<T> >;
template<class T> using MinHeap = priority_queue< T , vector<T> , greater<T> >;

constexpr ll dx[] = { 0 , 0 , -1 , 1 };
constexpr ll dy[] = { -1 , 1 , 0 , 0 };
const ll L = 2e3 + 5;
char fix[] = { '<' , '>' , '^' , 'v' };
char in[] = { '>' , '<' , 'v' , '^' };
char a[L][L];
ii en , st;
ll n, m;
ll d[L][L];
ii ret[L][L];
bool isValid( ll x , ll y ){
    char c = a[x][y];
    return x >= 1 && x <= n && y >= 1 && y <= m && c != 'x';
}
void dijkstra( ll rx , ll ry ){
    for ( int i = 1 ; i <= n ; i++ ){
        for ( int j = 1 ; j <= m ; j++ ){
            d[i][j] = LINF;
            ret[i][j] = { -1 , -1 };
        }
    }
    deque<ii> Q;
    Q.push_front({ rx, ry });
    d[rx][ry] = 0;
    while ( !Q.empty() ){
        auto [ x , y ] = Q.front();
        if ( Q.front() == st ) return;
        Q.pop_front();
        for ( int i = 0 ; i < 4 ; i++ ){
            ll nx = x + dx[i];
            ll ny = y + dy[i];
            if ( !isValid( nx , ny ) ) continue;
            ll cost = 1;
            if ( a[nx][ny] == in[i] ) cost = 0;
            if ( a[nx][ny] == 'o' ) cost = 0;
            if ( d[nx][ny] > d[x][y] + cost ){
                d[nx][ny] = d[x][y] + cost;
                ret[nx][ny] = { x, y };
                if (cost) Q.push_back({ nx , ny });
                else Q.push_front({ nx , ny });
            }
        }
    }
}
void Whisper(){
    cin >> n >> m;
    for ( int i = 1 ; i <= n ; i++ ){
        for ( int j = 1 ; j <= m ; j++ ){
            cin >> a[i][j];
            if ( a[i][j] == 'o' ){
                st = { i , j };
            }
            if ( a[i][j] == 'x' ){
                en = { i , j };
            }
        }
    }
    dijkstra( en.fi , en.se );
    cout << d[st.fi][st.se] << '\n';
    ii cur = st;
    while ( cur != en ){
        auto [ x , y ] = cur;
        ii go = ret[x][y];
        for ( int i = 0 ; i < 4 ; i++ ){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if ( nx == go.fi && ny == go.se ){
                if ( a[x][y] != 'o' )
                    a[x][y] = fix[i];
                cur = go;
            }
        }
    }
    a[en.fi][en.se] = 'x';
    for ( int i = 1 ; i <= n ; ++i ){
        for ( int j = 1 ; j <= m ; j++ )
            cout << a[i][j];
        cout << '\n';
    }
}

signed main(){
    cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr);
    #define TASK "__Whisper"
//    freopen(TASK".inp","r",stdin);
//    freopen(TASK".out","w",stdout);
    ll Test = 1; //cin >> Test;
    for ( int i = 1 ; i <= Test ; i++ ){

        Whisper();
        //
        cout << '\n';
    }
}

• Subtask 1: 30 / 30
• Subtask 2: 80 / 80