답안 #1094988

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1094988	2024-10-01T06:17:45 Z	Rafat	Mecho (IOI09_mecho)	C++14	45 / 100	453 ms	9632 KB

mecho

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <time.h>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <cstring>

using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <iostream>

using namespace __gnu_pbds;
using namespace std;
template <class T>
using Tree =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// to erase in multiset-> less_equal<T> and 
// s.erase(s.find_by_order(s.order_of_key(x)))
// lower_bound(x)=>(cannot use the stl lower_bound function)
// ll idx = s.order_of_key(x)
// if(idx == s.size()) -> no lower_bound
// else lb = *s.find_by_order(idx) // as 0-indexing
// idx-1 will give highest value which is strictly less than x
// for upper_bound->do the same with (x+1)

typedef long long ll;
typedef long double ld;
typedef pair<int,int> p32;
typedef pair<ll,ll> p64;
typedef tuple<ll, ll, ll> t64;
typedef vector<t64> vt64;
typedef vector<vt64> vvt64;
typedef pair<double,double> pdd;
typedef vector<ll> v64;
typedef vector<int> v32;
typedef vector<vector<int> > vv32;
typedef vector<vector<ll> > vv64;
typedef vector<vector<p64> > vvp64;
typedef vector<p64> vp64;
typedef vector<p32> vp32;
typedef vector<vector<p32> > vvp32;
typedef vector<bool> vb;
ll mod =  1e9+7, MOD = 998244353;
double eps = 1e-12;
// #define forn(i,e) for(ll i = 0; i < e; i++)
#define FOR(s, e, i) for(int i = s; i <= e; i++)
// #define rforn(i,s) for(ll i = s; i >= 0; i--)
#define ROF(s ,e, i) for(int i = s; i >= e; i--)
#define coutAll(A) for(auto asdafas : A) cout <<  asdafas << " "; cout << "\n";
#define foutAll(A) for(auto asdafas : A) fout <<  asdafas << " "; cout << "\n";
#define cinAll(A) for(auto &asdafas : A) cin >>  asdafas;
#define finAll(A) for(auto &asdafas : A) fin >>  asdafas;
#define minpq priority_queue<ll, v64, greater<ll>>
#define maxpq priority_queue<ll> 
#define ln "\n"
#define dbg(x) cout<<#x<<" = "<<x<<ln
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define fi first
#define se second
ll inf = LLONG_MAX;
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((ll)(x).size())
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef pair<ll, ll> pll;
typedef pair<ll, ll> pii;
//#define MAXN 1000000
struct info{
    int i, j, dist;
    bool isbear;
    // info(int x, int y, bool b) : i(x), j(y), dist(0), isbear(b){}
};
void solve(int it)
{
    ll n, s;
    cin >> n >> s;
    vector<string>A(n);
    cinAll(A);
    int bi, bj, hi, hj;
    vp32 hives;
    FOR(0, n - 1, i){
        FOR(0, n - 1, j){
            if(A[i][j] == 'D'){
                hi = i;
                hj = j;
                continue;
            }
            if(A[i][j] == 'M'){
                bi = i;
                bj = j;
                continue;
            }
            if(A[i][j] == 'H'){
                hives.emplace_back(i, j);
            }
        }
    }
    int dx[] = {1, -1, 0, 0};
    int dy[] = {0, 0, 1, -1};
    auto ok = [&](ll rest)->bool{
        // cout << rest << "\n";
        vv32 vis(n, v32(n));
        // 0->not occupied
        // 1->bee
        // 2->bear
        deque<info>q;
        q.push_back({bi, bj, 0, true});
        vis[bi][bj] = 2;
        for(auto x : hives){
            if(rest)
                q.push_front({x.fi, x.se, 0, false});
            else
                q.push_back({x.fi, x.se, 0, false});
            vis[x.fi][x.se] = 1;
        }
        while(!q.empty()){
            auto u = q.front();
            q.pop_front();
            // if(u.dist == rest) continue;
            if(u.isbear and vis[u.i][u.j] != 2) continue;
            // if(rest == 1){
            //     cout << (u.isbear ? "Bear" : "Bee") << " ";
            //     cout << u.i+1 << " " << u.j+1 << " " << u.dist << "\n";
            // }
            FOR(0, 3, i){
                int ni = u.i+dx[i];
                int nj = u.j+dy[i];
                    // if(rest == 1 && u.i == 3 && u.j == 3 && u.isbear){
                    //     cout << ni+1 << " " << nj+1 << " " << vis[ni][nj] << "->\n";
                    // }
                if(vis[u.i][u.j] == 1){
                    // bee
                    // if(rest == 1 && u.i == 3 && u.j == 3 && u.isbear){
                    //     cout << "bee " << ni+1 << " " << nj+1 << "->\n";
                    // }
                    if(
                        ni >= 0 && ni < n && nj >= 0 && nj < n
                        && A[ni][nj] != 'T'
                        && A[ni][nj] != 'D'
                        && vis[ni][nj] != 1
                    ){
                        vis[ni][nj] = 1;
                        if(u.dist+1 < rest)
                            q.push_front({ni, nj, u.dist+1, false});
                        else
                            q.push_back({ni, nj, u.dist+1, false});
                    }
                    continue;
                }
                //bear
                if(
                    ni >= 0 && ni < n && nj >= 0 && nj < n
                    && A[ni][nj] != 'T' && (vis[ni][nj] == 0 || 
                    (vis[ni][nj] == 2 && u.dist == 0))
                ){
                    // if(rest == 1 && u.i == 3 && u.j == 3 && u.isbear){
                    //     cout << ni+1 << " " << nj+1 << "\n";
                    // }
                    if(A[ni][nj] == 'D') return true;
                    vis[ni][nj] = 2;
                    if((u.dist+1)%s)
                        q.push_front({ni, nj, u.dist+1, true});
                    else
                        q.push_back({ni, nj, 0, true});
                }
            }
        }
        return false;
    };
    int l = 0, r = 1e6, ans = -1;
    while(l <= r){
        ll mid = (l + r) / 2;
        if(ok(mid)){
            ans = mid;
            l = mid + 1;
        }else{
            r = mid - 1;
        }
    }
    cout << ans;
}


int main()
{
    fast_cin();    
    ll t = 1;
    // cin >> t;
    for(int it=1; it<=t; it++)
    {
        //cout << "Case " << it << ": ";
        solve(it);
    }
    return 0;
}

Compilation message

mecho.cpp: In function 'void solve(int)':
mecho.cpp:90:17: warning: variable 'hi' set but not used [-Wunused-but-set-variable]
   90 |     int bi, bj, hi, hj;
      |                 ^~
mecho.cpp:90:21: warning: variable 'hj' set but not used [-Wunused-but-set-variable]
   90 |     int bi, bj, hi, hj;
      |                     ^~
mecho.cpp:119:19: warning: 'bj' may be used uninitialized in this function [-Wmaybe-uninitialized]
  119 |         vis[bi][bj] = 2;
      |                   ^
mecho.cpp:90:9: warning: 'bi' may be used uninitialized in this function [-Wmaybe-uninitialized]
   90 |     int bi, bj, hi, hj;
      |         ^~

Subtask #1

45.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Incorrect	435 ms	9632 KB	Output isn't correct
8	Correct	0 ms	344 KB	Output is correct
9	Incorrect	0 ms	348 KB	Output isn't correct
10	Correct	0 ms	348 KB	Output is correct
11	Incorrect	0 ms	348 KB	Output isn't correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	1 ms	492 KB	Output is correct
14	Correct	2 ms	348 KB	Output is correct
15	Correct	0 ms	460 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	1 ms	348 KB	Output is correct
20	Correct	1 ms	348 KB	Output is correct
21	Correct	1 ms	348 KB	Output is correct
22	Correct	1 ms	348 KB	Output is correct
23	Correct	1 ms	348 KB	Output is correct
24	Correct	1 ms	348 KB	Output is correct
25	Correct	1 ms	348 KB	Output is correct
26	Correct	1 ms	348 KB	Output is correct
27	Correct	1 ms	348 KB	Output is correct
28	Correct	1 ms	348 KB	Output is correct
29	Correct	2 ms	348 KB	Output is correct
30	Correct	1 ms	348 KB	Output is correct
31	Correct	2 ms	348 KB	Output is correct
32	Correct	2 ms	348 KB	Output is correct
33	Correct	32 ms	1212 KB	Output is correct
34	Correct	28 ms	1200 KB	Output is correct
35	Incorrect	52 ms	1628 KB	Output isn't correct
36	Correct	43 ms	1372 KB	Output is correct
37	Correct	39 ms	1372 KB	Output is correct
38	Incorrect	67 ms	1892 KB	Output isn't correct
39	Correct	53 ms	1664 KB	Output is correct
40	Correct	48 ms	1668 KB	Output is correct
41	Incorrect	84 ms	2392 KB	Output isn't correct
42	Correct	64 ms	1984 KB	Output is correct
43	Correct	61 ms	1984 KB	Output is correct
44	Incorrect	109 ms	2908 KB	Output isn't correct
45	Correct	86 ms	2256 KB	Output is correct
46	Correct	73 ms	2312 KB	Output is correct
47	Incorrect	132 ms	3524 KB	Output isn't correct
48	Correct	95 ms	2640 KB	Output is correct
49	Correct	87 ms	2628 KB	Output is correct
50	Incorrect	158 ms	3928 KB	Output isn't correct
51	Correct	123 ms	3020 KB	Output is correct
52	Correct	101 ms	3004 KB	Output is correct
53	Incorrect	193 ms	4700 KB	Output isn't correct
54	Correct	135 ms	3388 KB	Output is correct
55	Correct	124 ms	3672 KB	Output is correct
56	Incorrect	218 ms	5208 KB	Output isn't correct
57	Correct	155 ms	3836 KB	Output is correct
58	Correct	150 ms	3860 KB	Output is correct
59	Incorrect	255 ms	5980 KB	Output isn't correct
60	Correct	175 ms	4312 KB	Output is correct
61	Correct	174 ms	4288 KB	Output is correct
62	Incorrect	288 ms	6892 KB	Output isn't correct
63	Correct	368 ms	4316 KB	Output is correct
64	Incorrect	252 ms	4336 KB	Output isn't correct
65	Incorrect	366 ms	4312 KB	Output isn't correct
66	Correct	316 ms	4184 KB	Output is correct
67	Correct	335 ms	4188 KB	Output is correct
68	Correct	257 ms	4336 KB	Output is correct
69	Correct	233 ms	4184 KB	Output is correct
70	Correct	277 ms	4316 KB	Output is correct
71	Correct	258 ms	4328 KB	Output is correct
72	Correct	217 ms	4188 KB	Output is correct
73	Correct	292 ms	6364 KB	Output is correct
74	Incorrect	317 ms	6356 KB	Output isn't correct
75	Incorrect	329 ms	6400 KB	Output isn't correct
76	Incorrect	338 ms	6368 KB	Output isn't correct
77	Incorrect	352 ms	6300 KB	Output isn't correct
78	Correct	368 ms	6336 KB	Output is correct
79	Incorrect	280 ms	6744 KB	Output isn't correct
80	Incorrect	327 ms	6304 KB	Output isn't correct
81	Incorrect	412 ms	6560 KB	Output isn't correct
82	Incorrect	302 ms	6748 KB	Output isn't correct
83	Incorrect	453 ms	6488 KB	Output isn't correct
84	Incorrect	349 ms	6488 KB	Output isn't correct
85	Incorrect	284 ms	6616 KB	Output isn't correct
86	Incorrect	352 ms	6636 KB	Output isn't correct
87	Incorrect	356 ms	6488 KB	Output isn't correct
88	Incorrect	374 ms	7380 KB	Output isn't correct
89	Incorrect	349 ms	7284 KB	Output isn't correct
90	Incorrect	405 ms	7372 KB	Output isn't correct
91	Incorrect	361 ms	7268 KB	Output isn't correct
92	Incorrect	450 ms	7276 KB	Output isn't correct