제출 #999595

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
999595		Hadi_Alhamed	Mecho (IOI09_mecho)	C++17	11 / 100	55 ms	46420 KiB

mecho

// to live is to die
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef long long int ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpl;
#define Clear(a, n)              \
    for (int i = 0; i <= n; i++) \
    {                            \
        a[i] = 0;                \
    }
#define clearMat(a, n, m, d)         \
    for (int i = 0; i <= n; i++)     \
    {                                \
        for (int j = 0; j <= m; j++) \
            a[i][j] = d;             \
    }
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define PB push_back
#define PF push_front
#define MP make_pair
#define F first
#define S second
#define rep(i, n) for (int i = 0; i < n; i++)
#define repe(i, j, n) for (int i = j; i < n; i++)
#define SQ(a) (a) * (a)
#define rep1(i, n) for (int i = 1; i <= n; i++)
#define Rrep(i, start, finish) for (int i = start; start >= finish; i--)

#define forn(i, Start, End, step) for (int i = Start; i <= End; i += step)
#define rforn(i, Start, End, step) for (int i = Start; i >= End; i -= step)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
// ll arr[SIZE];
/*
how to find n % mod ; n < 0?
x = (n+mod)%mod
if(x < 0) x += mod;
*/
void __print(int x)
{
    cerr << x;
}
void __print(long x)
{
    cerr << x;
}
void __print(long long x)
{
    cerr << x;
}
void __print(unsigned x)
{
    cerr << x;
}
void __print(unsigned long x)
{
    cerr << x;
}
void __print(unsigned long long x)
{
    cerr << x;
}
void __print(float x)
{
    cerr << x;
}
void __print(double x)
{
    cerr << x;
}
void __print(long double x)
{
    cerr << x;
}
void __print(char x)
{
    cerr << '\'' << x << '\'';
}
void __print(const char *x)
{
    cerr << '\"' << x << '\"';
}
void __print(const string &x)
{
    cerr << '\"' << x << '\"';
}
void __print(bool x)
{
    cerr << (x ? "true" : "false");
}

template<typename T, typename V>
void __print(const pair<T, V> &x)
{
    cerr << '{';
    __print(x.first);
    cerr << ',';
    __print(x.second);
    cerr << '}';
}
template<typename T>
void __print(const T &x)
{
    int f = 0;
    cerr << '{';
    for (auto &i: x) cerr << (f++ ? "," : ""), __print(i);
    cerr << "}";
}
void _print()
{
    cerr << "]\n";
}
template <typename T, typename... V>
void _print(T t, V... v)
{
    __print(t);
    if (sizeof...(v)) cerr << ", ";
    _print(v...);
}
#ifndef ONLINE_JUDGE
#define db(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define db(x...)
#endif

// order_of_key(k): # of elements less than k (which is the index of x = k)
// find_by_order(k); iterator of the k-th element

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T>
bool ckmin(T &a, const T &b)
{
    return b < a ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T &a, const T &b)
{
    return a < b ? a = b, 1 : 0;
}
template <typename T>
istream &operator>>(istream &in, vector<T> &a)
{
    for (auto &x : a)
        in >> x;
    return in;
};
template <typename T>
ostream &operator<<(ostream &out, vector<T> &a)
{
    for (auto &x : a)
        out << x << ' ';
    return out;
};

// priority_queue<data type , the container that would hold the values , greater<pair<int,int>>>
// greater means that we want the smallest value on top
// less means that we want the largest
// x ^ (n) mod m = ( (x mod m)^(n) ) mod m
char to_char(int num)
{
    return (char)(num + '0');
}

ll const MAX = 1e18 + 1;
ll const oo = 1e18 + 1;
ll const INF = 1e9 + 10;
const ll MOD = 998244353;
ll const SIZE = 2e5 + 900;
const int LOG = 20;

template <typename T, typename T2>
ll add(T X, T2 Y)
{
    X += Y;
    if (X >= MOD)
    {
        X -= MOD;
    }
    return X;
}
template <typename T, typename T2>

ll sub(T  X , T2 Y)
{
    X -= Y;
    if(X < 0) X += MOD;
    return X;
}

template <typename T, typename T2>
T mult(T X, T2 Y)
{
    return X * Y % MOD;
}

void setIO(string s)
{
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}
// x & (-x) give me the minBit of x
//  x & (x - 1) turns off rightmost bit
int dist[3][1003][1003];
bool vis[1003][1003];
int dx[4] = {0 , 0 , 1 , -1};
int dy[4] = {1 , -1 , 0 , 0};
void solve()
{
        //M , G : YES
        //T , H : NO;
        // he can make S steps by minute
        //every minute each bee hive spread to its 4 adjacent cells
        int N , S;
        cin >> N >> S;
        vector<string>mat(N);
        vpi hives;
        int Dx{} , Dy{};
        int mx{} , my{};
        rep(i , N)
        {
            cin >> mat[i];
            rep(j , N)
            {
                dist[0][i][j] = dist[1][i][j] = 2e9;
                if(mat[i][j] == 'H')
                {
                    hives.PB({i , j});
                }
                if(mat[i][j] == 'D')
                {
                    Dx = i ; Dy = j;
                }
                if(mat[i][j] == 'M')
                {
                    mx = i ; my = j;
                }
            }
        }
        auto valid = [&](int x , int y)
        {
                return x >= 0 && x < N && y < N && y >= 0;
        };
        function<void(vpi , bool)> BFS = [&](vpi sources , bool ty)
        {
                queue<pi>Q;
                for(auto [x , y] : sources)
                {
                    Q.push({x, y});
                    dist[ty][x][y] = 0;
                }
                while(!Q.empty())
                {
                    pi cur = Q.front();
                    Q.pop();
                    int x = cur.F;
                    int y = cur.S;
                    for(int i = 0 ; i < 4 ; i++)
                    {
                        int _x = x + dx[i];
                        int _y = y + dy[i];
                        if(!valid(_x , _y))continue;
                        if(ty == 0)
                        {
                            //i am M
                            if(mat[_x][_y] == 'H' || mat[_x][_y] == 'T')continue;
                        }
                        if(ty == 1)
                        {
                            //a bee
                            if(mat[_x][_y] == 'D' || mat[_x][_y] == 'T')continue;
                        }
                        if(dist[ty][_x][_y] > dist[ty][x][y] + 1)
                        {
                            dist[ty][_x][_y] = dist[ty][x][y] + 1;
                            Q.push({_x , _y});
                        }
                    }
                }
        };
        BFS(vpi{{mx , my}} , 0);
        BFS(hives , 1);
        int answer = -1;
        function<void(int , int , int)> DFS = [&](int x , int y , int min_possible)->void
        {
                vis[x][y] = 1;

                for(int i = 0 ;i < 4 ; i++)
                {
                        int _x = x + dx[i];
                        int _y = y + dy[i];
                        if(!valid(_x , _y) || mat[_x][_y] == 'T' || mat[_x][_y] == 'H' || vis[_x][_y])continue;
                        int Mm = (dist[0][_x][_y] + S - 1)/S;// ceil or floor?
                        int Ms = dist[0][_x][_y];
                        int Hm = dist[1][_x][_y];
                        int Hs = dist[1][_x][_y] * S;
                        int dif{};
                        if(Hs < Ms)
                        {
                            continue;//cannot go there
                        }
                        if(Hs == Ms)
                        {
                            dif = 0;
                        }else // Hs  > Ms , how much we can stay eating
                        {
                            dif = Hm - Mm;
                        }

                        if(_x == Dx && _y == Dy)
                        {
                            answer = max(answer , min(dif , min_possible));
//                            db(x , y , dif , answer);

                        }
                        DFS(_x , _y , min(min_possible , dif));
                }
        };
        DFS(mx,  my  , 2e9);
        cout << answer << "\n";
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    setIO("atlarge");
    int T = 1;
//    cin >> T;

    while (T--)
    {
        solve();
    }
    return 0;
}

/* stuff you should look for
 * WRITE STUFF DOWN,  ON PAPER
 * BFS THEN DFS
 * int overflow, array bounds
 * special cases (n=1?)
 * do sm th instead of nothing and stay organized
 * DON'T GET STUCK ON ONE APPROACH
 * (STUCK?)******** Try to simplify the problem(keeping in mind the main problem), ():
 * 1- problem to subProblem
 * 2- from simple to complex: start with a special
 *    problem and then try to update the solution for general case
 *    -(constraints - > solve it with none , one,two ... of them till you reach the given problem
      -(no constraints - > try to give it some)
      -how a special case may be incremented
 * 3-Simplification by Assumptions
 * REVERSE PROBLEM
 * PROBLEM ABSTRACTION
 * SMALL O BSERVATIONS MIGHT HELP ALOT
 * WATCH OUT FOR TIME
 * RETHINK YOUR IDEA,BETTER IDEA, APPROACH?
 * CORRECT IDEA, NEED MORE OBSERVATIONS
 * CORRECT APPROACH, WRONG IDEA
 * WRONG APPROACH
 * THINK CONCRETE THEN SYMBOL,
 * having the solution for the first m state , can we solve it for m + 1 ?
 * in many cases incremental thinking needs data sorting
 */

컴파일 시 표준 에러 (stderr) 메시지

mecho.cpp: In function 'void setIO(std::string)':
mecho.cpp:212:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  212 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:213:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  213 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 100