Submission #999597

#TimeUsernameProblemLanguageResultExecution timeMemory
999597Hadi_AlhamedMecho (IOI09_mecho)C++17
100 / 100
127 ms13916 KiB
// 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}; int mn[1003][1003]; 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; mn[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_bee = [&](int x , int y) { return x >= 0 && x < N && y < N && y >= 0 && mat[x][y] != 'T' && mat[x][y] != 'D' && dist[1][x][y] == 2e9; }; auto valid_M = [&](int x , int y) { return x >= 0 && x < N && y < N && y >= 0 && mat[x][y] != 'T' && mat[x][y] != 'H' && dist[0][x][y] == -1; }; function<void(vpi)> multisource_BFS = [&](vpi sources) { queue<pi>Q; for(auto [x , y] : sources) { Q.push({x, y}); dist[1][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_bee(_x , _y))continue; dist[1][_x][_y] = dist[1][x][y] + 1; Q.push({_x , _y}); } } }; auto can_go = [&](int x, int y)->bool { return x/S < y; }; function<bool(int)> is_good = [&](int mid)->bool { //mid : minutes he can spend eating honey if(dist[1][mx][my] <= mid)return 0; memset(dist[0] , -1 , sizeof dist[0]); dist[0][mx][my] = 0; queue<pi> Q; Q.push({mx , my}); while(!Q.empty()) { pi cur = Q.front(); Q.pop(); int x = cur.F; int y = cur.S; rep(i , 4) { int _x = x + dx[i]; int _y = y + dy[i]; if(!valid_M(_x , _y))continue; if(_x == Dx && _y == Dy)return true; if(can_go(dist[0][x][y] + 1 , dist[1][_x][_y] - mid)) { dist[0][_x][_y] = dist[0][x][y] + 1; Q.push({_x , _y}); } } } return dist[0][Dx][Dy] != -1; }; multisource_BFS(hives); int L = 0 , R = 1e6; int answer = -1; while(L <= R) { int mid = (L + R)/2; if(is_good(mid)) { answer = mid; L = mid + 1; }else{ R = mid - 1; } } 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 */

Compilation message (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);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...