oj.uz

Submission #1054504

# Submission time Handle Problem Language Result Execution time Memory
1054504 2024-08-12T10:19:50 Z Nonoze Mecho (IOI09_mecho) C++17
30 / 100
 788 ms 47960 KB 
/*
*	Author: Nonoze
*	Created: Wednesday 07/08/2024
*/
#include <bits/stdc++.h>
using namespace std;


namespace std {

// https://judge.yosupo.jp/submission/193613
struct IOPre {
    static constexpr int TEN = 10, SZ = TEN * TEN * TEN * TEN;
    std::array<char, 4 * SZ> num;
    constexpr IOPre() : num{} {
        for (int i = 0; i < SZ; i++) for (int n = i, j = 3; j >= 0; j--) num[i * 4 + j] = n % TEN + '0', n /= TEN;
    }
};

struct IO {
#if !HAVE_DECL_FREAD_UNLOCKED
    #define fread_unlocked fread
#endif
#if !HAVE_DECL_FWRITE_UNLOCKED
    #define fwrite_unlocked fwrite
#endif
    static constexpr int SZ = 1 << 17, LEN = 32, TEN = 10, HUNDRED = TEN * TEN,
                         THOUSAND = HUNDRED * TEN, TENTHOUSAND = THOUSAND * TEN,
                         MAGIC_MULTIPLY = 205, MAGIC_SHIFT = 11, MASK = 15,
                         TWELVE = 12, SIXTEEN = 16;
    static constexpr IOPre io_pre = {};
    std::array<char, SZ> input_buffer, output_buffer;
    int input_ptr_left, input_ptr_right, output_ptr_right;

    IO() : input_buffer{}, output_buffer{}, input_ptr_left{}, input_ptr_right{}, output_ptr_right{} {}
    IO(const IO&) = delete;
    IO(IO&&) = delete;
    IO& operator=(const IO&) = delete;
    IO& operator=(IO&&) = delete;
    ~IO() { flush(); }

    template<typename T> static constexpr bool is_char_v    = std::is_same_v<T, char>;
    template<typename T> static constexpr bool is_bool_v    = std::is_same_v<T, bool>;
    template<typename T> static constexpr bool is_string_v  =
            std::is_same_v<T, std::string> || std::is_same_v<T, const char*> ||
            std::is_same_v<T, char*> || std::is_same_v< std::decay_t<T>, char*>;
    template<typename T> static constexpr bool is_default_v =
            is_char_v<T> || is_bool_v<T> || is_string_v<T> || std::is_integral_v<T>;

    inline void load() {
        memmove(std::begin(input_buffer),
                std::begin(input_buffer) + input_ptr_left,
                input_ptr_right - input_ptr_left);
        input_ptr_right =
            input_ptr_right - input_ptr_left +
            fread_unlocked(
                std::begin(input_buffer) + input_ptr_right - input_ptr_left, 1,
                SZ - input_ptr_right + input_ptr_left, stdin);
        input_ptr_left = 0;
    }

    inline void read_char(char& c) {
        if (input_ptr_left + LEN > input_ptr_right) load();
        c = input_buffer[input_ptr_left++];
    }
    inline void read_string(std::string& x) {
        char c;
        while (read_char(c), c < '!') continue;
        x = c;
        while (read_char(c), c >= '!') x += c;
    }
    template<typename T>
    inline std::enable_if_t<std::is_integral_v<T>, void> read_int(T& x) {
        if (input_ptr_left + LEN > input_ptr_right) load();
        char c = 0;
        do c = input_buffer[input_ptr_left++];
        while (c < '-');
        [[maybe_unused]] bool minus = false;
        if constexpr (std::is_signed<T>::value == true)
            if (c == '-') minus = true, c = input_buffer[input_ptr_left++];
        x = 0;
        while (c >= '0')
            x = x * TEN + (c & MASK), c = input_buffer[input_ptr_left++];
        if constexpr (std::is_signed<T>::value == true)
            if (minus) x = -x;
    }

    inline void skip_space() {
        if (input_ptr_left + LEN > input_ptr_right) load();
        while (input_buffer[input_ptr_left] <= ' ') input_ptr_left++;
    }

    inline void flush() {
        fwrite_unlocked(std::begin(output_buffer), 1, output_ptr_right, stdout);
        output_ptr_right = 0;
    }

    inline void write_char(char c) {
        if (output_ptr_right > SZ - LEN) flush();
        output_buffer[output_ptr_right++] = c;
    }

    inline void write_bool(bool b) {
        if (output_ptr_right > SZ - LEN) flush();
        output_buffer[output_ptr_right++] = b ? '1' : '0';
    }

    inline void write_string(const std::string& s) {
        for (auto x : s) write_char(x);
    }

    inline void write_string(const char* s) {
        while (*s) write_char(*s++);
    }

    inline void write_string(char* s) {
        while (*s) write_char(*s++);
    }

    template <typename T>
    inline std::enable_if_t< std::is_integral_v<T>, void> write_int(T x) {
        if (output_ptr_right > SZ - LEN) flush();
        if (!x) {
            output_buffer[output_ptr_right++] = '0';
            return;
        }
        if constexpr (std::is_signed_v<T>) if (x < 0) output_buffer[output_ptr_right++] = '-', x = -x;
        int i = TWELVE;
        std::array<char, SIXTEEN> buf{};
        for (; x >= TENTHOUSAND; x /= TENTHOUSAND, i -= 4)
            memcpy(std::begin(buf) + i, std::begin(io_pre.num) + (x % TENTHOUSAND) * 4, 4);
        if (x < HUNDRED) {
            if (x < TEN) output_buffer[output_ptr_right++] = '0' + x;
            else {
                uint32_t q = (uint32_t(x) * MAGIC_MULTIPLY) >> MAGIC_SHIFT;
                uint32_t r = uint32_t(x) - q * TEN;
                output_buffer[output_ptr_right++] = '0' + q;
                output_buffer[output_ptr_right++] = '0' + r;
            }
        } else {
            if (x < THOUSAND) 
                memcpy(std::begin(output_buffer) + output_ptr_right, std::begin(io_pre.num) + (x << 2) + 1, 3),
                output_ptr_right += 3;
            else
                memcpy(std::begin(output_buffer) + output_ptr_right, std::begin(io_pre.num) + (x << 2), 4),
                output_ptr_right += 4;
        }
        memcpy(std::begin(output_buffer) + output_ptr_right, std::begin(buf) + i + 4, TWELVE - i);
        output_ptr_right += TWELVE - i;
    }

    template <typename T_>
    std::enable_if_t<(is_default_v< std::remove_cv_t< std::remove_reference_t<T_> > >), IO&> operator<<(T_&& x) {
        using T = std::remove_cv_t< std::remove_reference_t<T_> >;
        if constexpr (is_bool_v<T>) write_bool(x);
        else if constexpr (is_string_v<T>) write_string(x);
        else if constexpr (is_char_v<T>) write_char(x);
        else if constexpr (std::is_integral_v<T>) write_int(x);
        return *this;
    }

    template<typename T>
    std::enable_if_t<(is_default_v<T> && !is_bool_v<T>), IO&> operator>>(T& x) {
        if constexpr (is_string_v<T>) read_string(x);
        else if constexpr (is_char_v<T>) read_char(x);
        else if constexpr (std::is_integral_v<T>) read_int(x);
        return *this;
    }

    IO* tie(std::nullptr_t) { return this; }
    void sync_with_stdio(bool) {}
} io;

} // namespace std

using std::io;

#define cin io
#define cout io


#ifndef _IN_LOCAL
	#define dbg(...)
#endif

#define endl '\n'
#define endlfl '\n' << flush
#define quit(x) return (void)(cout << x << endl)

template<typename T> void read(T& x) { cin >> x; }
template<typename T1, typename T2> void read(pair<T1, T2>& p) { read(p.first), read(p.second); }
template<typename T> void read(vector<T>& v) { for (auto& x : v) read(x); }
template<typename T1, typename T2> void read(T1& x, T2& y) { read(x), read(y);}
template<typename T1, typename T2, typename T3> void read(T1& x, T2& y, T3& z) { read(x), read(y), read(z); }
template<typename T1, typename T2, typename T3, typename T4> void read(T1& x, T2& y, T3& z, T4& zz) { read(x), read(y), read(z), read(zz); }
template<typename T> void print(vector<T>& v) { for (auto& x : v) cout << x << ' '; cout << endl; }


#define sz(x) (int)(x.size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define cmin(a, b) a = min(a, b)
#define cmax(a, b) a = max(a, b)

#define int long long
const int inf = numeric_limits<int>::max() / 4;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MOD = 1e9+7, LOG=25;



void solve();

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tt=1;
	// cin >> tt;
	while(tt--) solve();
	return 0;
}




int n, k, s, t;
vector<int> h;
vector<vector<int>> adj;
vector<bool> bees, visited;

bool propagate(queue<pair<int, pair<int, int>>> &q, bool bee, int comp) {
	int limit=q.front().se.se;
	while (!q.empty() && q.front().se.se<=limit) {
		int u=q.front().fi, nb=q.front().se.fi, time=q.front().se.se; q.pop();
		for (auto v: adj[u]) {
			if (bees[v] || (!bee && visited[v])) continue;
			if (bee && t==v) continue;
			if (bee) bees[v]=1;
			else visited[v]=1;
			if (!bee && v==t) return 1;
			if (nb+1>=comp) q.push({v, {0, time+1}});
			else q.push({v, {nb+1, time}});
		}
	}
	return 0;
}


bool ok(int wait) {
	bees.clear(), visited.clear(), bees.resize(n, 0), visited.resize(n, 0); visited[s]=1;
	for (auto u: h) bees[u]=1;
	queue<pair<int, pair<int, int>>> qbees;
	queue<pair<int, pair<int, int>>> q2; q2.push({s, {0, 0}});
	for (auto u: h) qbees.push({u, {0, 0}});
	propagate(qbees, 1, wait);
	while (!q2.empty()) {
		if (propagate(q2, 0, k)) return 1;
		propagate(qbees, 1, 1);
	}
	return 0;
}


void solve() {
	read(n, k);
	vector<string> a(n, string(n, '.')); 
	for (int i=0; i<n; i++) {
		for (int j=0; j<n; j++) cin >> a[i][j];
		char x; cin >> x;
	}
	adj.clear(), adj.resize(n*n);
	for (int i=0; i<n; i++) {
		for (int j=0; j<n; j++) {
			if (a[i][j]=='T') continue;
			int act=i*n+j;
			if (i && a[i-1][j]!='T') {
				int nxt=(i-1)*n+j;
				adj[act].pb(nxt), adj[nxt].pb(act);
			}
			if (j && a[i][j-1]!='T') {
				int nxt=i*n+j-1;
				adj[act].pb(nxt), adj[nxt].pb(act);
			}
			if (a[i][j]=='M') s=act;
			if (a[i][j]=='D') t=act;
			if (a[i][j]=='H') h.pb(act);
		}
	}
	n*=n;
	int ans=-1, l=0, r=n/2;
	while (l<=r) {
		int mid=(l+r)/2;
		if (ok(mid)) ans=mid, l=mid+1;
		else r=mid-1;
	}
	cout << ans << endl;
}

Subtask #1
30.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 600 KB Output isn't correct
2 Incorrect 1 ms 604 KB Output isn't correct
3 Incorrect 0 ms 604 KB Output isn't correct
4 Incorrect 0 ms 720 KB Output isn't correct
5 Incorrect 0 ms 604 KB Output isn't correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 785 ms 47440 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Correct 0 ms 604 KB Output is correct
12 Incorrect 1 ms 860 KB Output isn't correct
13 Incorrect 1 ms 716 KB Output isn't correct
14 Correct 1 ms 856 KB Output is correct
15 Incorrect 1 ms 600 KB Output isn't correct
16 Correct 0 ms 604 KB Output is correct
17 Incorrect 0 ms 720 KB Output isn't correct
18 Correct 0 ms 604 KB Output is correct
19 Incorrect 0 ms 604 KB Output isn't correct
20 Correct 0 ms 604 KB Output is correct
21 Incorrect 1 ms 720 KB Output isn't correct
22 Correct 1 ms 604 KB Output is correct
23 Incorrect 1 ms 604 KB Output isn't correct
24 Correct 0 ms 604 KB Output is correct
25 Incorrect 1 ms 860 KB Output isn't correct
26 Correct 1 ms 860 KB Output is correct
27 Incorrect 1 ms 860 KB Output isn't correct
28 Correct 1 ms 856 KB Output is correct
29 Incorrect 1 ms 860 KB Output isn't correct
30 Correct 1 ms 860 KB Output is correct
31 Incorrect 1 ms 860 KB Output isn't correct
32 Correct 1 ms 860 KB Output is correct
33 Incorrect 23 ms 5808 KB Output isn't correct
34 Correct 13 ms 5724 KB Output is correct
35 Correct 46 ms 7516 KB Output is correct
36 Incorrect 24 ms 7256 KB Output isn't correct
37 Correct 19 ms 7512 KB Output is correct
38 Correct 41 ms 9816 KB Output is correct
39 Incorrect 29 ms 9052 KB Output isn't correct
40 Correct 21 ms 9052 KB Output is correct
41 Correct 45 ms 12124 KB Output is correct
42 Incorrect 36 ms 10832 KB Output isn't correct
43 Correct 41 ms 10844 KB Output is correct
44 Correct 55 ms 14940 KB Output is correct
45 Incorrect 49 ms 13148 KB Output isn't correct
46 Correct 41 ms 13148 KB Output is correct
47 Correct 87 ms 17756 KB Output is correct
48 Incorrect 59 ms 15448 KB Output isn't correct
49 Correct 40 ms 15448 KB Output is correct
50 Correct 95 ms 21084 KB Output is correct
51 Incorrect 65 ms 18008 KB Output isn't correct
52 Correct 49 ms 18012 KB Output is correct
53 Correct 126 ms 24664 KB Output is correct
54 Incorrect 76 ms 20828 KB Output isn't correct
55 Correct 54 ms 20824 KB Output is correct
56 Correct 159 ms 28508 KB Output is correct
57 Incorrect 86 ms 23896 KB Output isn't correct
58 Correct 66 ms 23896 KB Output is correct
59 Correct 231 ms 32748 KB Output is correct
60 Incorrect 115 ms 27228 KB Output isn't correct
61 Correct 74 ms 26972 KB Output is correct
62 Correct 278 ms 37056 KB Output is correct
63 Incorrect 225 ms 30544 KB Output isn't correct
64 Correct 277 ms 30552 KB Output is correct
65 Correct 301 ms 30544 KB Output is correct
66 Incorrect 339 ms 30740 KB Output isn't correct
67 Correct 299 ms 30556 KB Output is correct
68 Incorrect 318 ms 30804 KB Output isn't correct
69 Correct 307 ms 30752 KB Output is correct
70 Correct 326 ms 30812 KB Output is correct
71 Correct 294 ms 30812 KB Output is correct
72 Incorrect 354 ms 30600 KB Output isn't correct
73 Incorrect 486 ms 47784 KB Output isn't correct
74 Correct 553 ms 47808 KB Output is correct
75 Correct 675 ms 47820 KB Output is correct
76 Correct 646 ms 47780 KB Output is correct
77 Correct 547 ms 47816 KB Output is correct
78 Correct 589 ms 47960 KB Output is correct
79 Correct 552 ms 47700 KB Output is correct
80 Correct 628 ms 47700 KB Output is correct
81 Correct 573 ms 47728 KB Output is correct
82 Correct 622 ms 47700 KB Output is correct
83 Incorrect 646 ms 47532 KB Output isn't correct
84 Correct 641 ms 47508 KB Output is correct
85 Correct 788 ms 47440 KB Output is correct
86 Correct 695 ms 47616 KB Output is correct
87 Correct 643 ms 47440 KB Output is correct
88 Incorrect 704 ms 47476 KB Output isn't correct
89 Correct 572 ms 47344 KB Output is correct
90 Correct 585 ms 47440 KB Output is correct
91 Correct 611 ms 47688 KB Output is correct
92 Correct 648 ms 47436 KB Output is correct