답안 #802805

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
802805	2023-08-02T14:43:05 Z	_VIBE	Mecho (IOI09_mecho)	C++17	33 / 100	146 ms	3796 KB

mecho

#include "bits/stdc++.h"
 
using namespace std;
 
#define ll long long int
#define pll pair<ll,ll> 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update>
typedef tree<pll, null_type,less<pll>, rb_tree_tag,tree_order_statistics_node_update>ordered_multiset;
#define ugp gp_hash_table<ll,ll,custom_hash>
#define umap unordered_map<ll,ll,custom_hash>
#define pb push_back
#define len(v) ((ll)(v.size()))
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define ff first
#define ss second
#define inp(a) for(auto &x:a) cin>>x;
#define vll vector<ll>
#define vvll vector<vector<ll>>
#define vs vector<string>
#define vpll vector<pair<ll,ll>> 
#define pn cout<<"NO\n"
#define py cout<<"YES\n"
#define mid(s,e) s+(e-s)/2
#define endl '\n'
const ll MAX_SIZE = 200005;
const ll ninf = (-1)*(1ll<<60);
const ll inf = 1ll<<60;
const ll mod = 1000000007;

//typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
#else
#define debug(x)
#endif

void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(lld t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(ull t) {cerr << t;}

template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

ll setbits(ll x){
    return __builtin_popcountll(x);
}
ll tz(ll x){
    return __builtin_ctz(x);
}
ll fastpow(ll a ,ll b){
    ll res=1;
    while(b){
       if(b&1) res*=a;
       a*=a;
       b/=2;
    }
    return res;
}
//bitset<1000001> isprime; 
//void seive(){
//    isprime.set();
//    isprime[1]=0;
//    for(ll i=4;i<MAX_SIZE;i+=2) isprime[i]=false;
//
//    for(ll i=3;i<MAX_SIZE;i+=2){
//        if(isprime[i]){
//            ll j=i;
//            while(j*i<MAX_SIZE){
//                isprime[j*i]=false;
//                j+=2;
//            }
//        }
//    }
//
//} 


ll t[4*MAX_SIZE];


int x,y;
int n,step_size;
int tx,ty;
vector<vector<char>> g;
vector<vector<int>> timer;

bool isvalid1(int i,int j){
    if(i<0 || i>=n || j<0 || j>=n) return false;
    if(g[i][j]=='H' || g[i][j]=='T') return false;
    return true;
}


vector<pair<int,int>> movem={{1,0},{-1,0},{0,1},{0,-1}};

bool check(int time){
    
    
    
    queue<pair<pair<int,int>,int>> q;
    q.push({{x,y},0});
    
    
    vector<vector<bool>> vis(n,vector<bool>(n,false));
    
    vis[x][y]=true;
    
    while(!q.empty()){
        
        pair<pair<int,int>,int> p=q.front();
        q.pop();
        int i=p.ff.ff,j=p.ff.ss;
        int s=p.ss;
        
        
        
        if(timer[i][j]<=(time+s/step_size)) continue;
        
        
        for(auto p1:movem){
            int i1=i+p1.ff;
            int j1=j+p1.ss;
            if(isvalid1(i1,j1) && !vis[i1][j1]){
              q.push({{i1,j1},s+1});
              vis[i1][j1]=true;
              if(i1==tx && j1==ty) return true;  
            } 
        }
        
        
   
    }
    
    
    return false;
    
    
    
    
    
    
}


bool isvalid(int i,int j){
    
    if(i<0 || i>=n || j<0 || j>=n) return false;
    
    if(g[i][j]=='T' || g[i][j]=='D') return false;
    
    return true;
    
}
 


void VIBE_KA_CODE(ll TC)
{
    cin>>n>>step_size;
    
    g.resize(n,vector<char>(n));
    
    
    timer.resize(n,vector<int>(n,1e9));
    
    
    queue<pair<int,int>> q;
    
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>g[i][j];
            if(g[i][j]=='M'){
                x=i;y=j;
            }
            if(g[i][j]=='H'){
                q.push({i,j});
                timer[i][j]=0;
            }
            if(g[i][j]=='D'){
                tx=i;ty=j;
            }
        }
    }
    
    
    while(!q.empty()){
        
        pair<int,int> p=q.front();
        q.pop();
        
        for(auto p1:movem){
            int i1=p.ff+p1.ff;
            int j1=p.ss+p1.ss;
            if(isvalid(i1,j1) && timer[i1][j1]>timer[p.ff][p.ss]+1){
                q.push({i1,j1});
                timer[i1][j1]=timer[p.ff][p.ss]+1;
            }
        }
        
    }
    
    
   
    
    
    
    
    
    int low=0,high=g[x][y]+5;
    int ans=-1;
    
    while(low<=high){
        
        
        int m=mid(low,high); 
        
        if(check(m)){
            ans=m;
            low=m+1;
        }
        else{
            high=m-1;
        } 
        
    }
    
    
    cout<<ans;
    
    
    
    
    
    
    
}
 
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    #ifndef ONLINE_JUDGE
    freopen("Error.txt", "w", stderr);
    #endif
    
     #ifdef ONLINEJUDGE
       freopen("input.txt","r",stdin); //can need to change file . this one for taking input
       freopen("output.txt","w",stdout); // this one for output
     #endif

    //seive();
    ll Tc=1;
    // cin>>Tc;
 
    for(ll tc=1;tc<=Tc;tc++)
    {
        VIBE_KA_CODE(tc);
    }
 
return 0;
}
/*
1. Initialize all variables! Arrays etc.
2. Min of Max and Max of Min, such type of problems usually require Binary Search
3. Use to_string and stoi,atoi for conversions to suitable types.
4. For setting precision of n digits after decimal, use cout<<fixed;cout<<setprecision(n); before output, or at start of code if all outputs have same precision(include ios and iomanip header files.
5. Instead os using ceil(a/b), use (a+b-1)/b or (a-1)/b+1.
6. For char to int, subtract '0', for int to char add'0'
*/

Compilation message

mecho.cpp: In function 'int main()':
mecho.cpp:277:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  277 |     freopen("Error.txt", "w", stderr);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

33.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	224 KB	Output is correct
7	Correct	67 ms	3648 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Incorrect	0 ms	340 KB	Output isn't correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Incorrect	1 ms	212 KB	Output isn't correct
16	Correct	0 ms	340 KB	Output is correct
17	Incorrect	0 ms	340 KB	Output isn't correct
18	Incorrect	0 ms	340 KB	Output isn't correct
19	Incorrect	0 ms	340 KB	Output isn't correct
20	Incorrect	0 ms	340 KB	Output isn't correct
21	Incorrect	0 ms	340 KB	Output isn't correct
22	Incorrect	0 ms	340 KB	Output isn't correct
23	Incorrect	0 ms	340 KB	Output isn't correct
24	Incorrect	0 ms	340 KB	Output isn't correct
25	Incorrect	1 ms	340 KB	Output isn't correct
26	Incorrect	1 ms	340 KB	Output isn't correct
27	Incorrect	1 ms	340 KB	Output isn't correct
28	Incorrect	0 ms	340 KB	Output isn't correct
29	Incorrect	1 ms	340 KB	Output isn't correct
30	Incorrect	1 ms	268 KB	Output isn't correct
31	Incorrect	1 ms	340 KB	Output isn't correct
32	Incorrect	1 ms	340 KB	Output isn't correct
33	Incorrect	4 ms	980 KB	Output isn't correct
34	Incorrect	3 ms	980 KB	Output isn't correct
35	Correct	16 ms	1016 KB	Output is correct
36	Incorrect	6 ms	1108 KB	Output isn't correct
37	Incorrect	4 ms	1156 KB	Output isn't correct
38	Correct	25 ms	1108 KB	Output is correct
39	Incorrect	5 ms	1364 KB	Output isn't correct
40	Incorrect	5 ms	1364 KB	Output isn't correct
41	Correct	27 ms	1360 KB	Output is correct
42	Incorrect	6 ms	1620 KB	Output isn't correct
43	Incorrect	6 ms	1620 KB	Output isn't correct
44	Correct	33 ms	1660 KB	Output is correct
45	Incorrect	9 ms	1876 KB	Output isn't correct
46	Incorrect	7 ms	1876 KB	Output isn't correct
47	Correct	44 ms	1924 KB	Output is correct
48	Incorrect	9 ms	2144 KB	Output isn't correct
49	Incorrect	8 ms	2140 KB	Output isn't correct
50	Correct	50 ms	2232 KB	Output is correct
51	Incorrect	9 ms	2516 KB	Output isn't correct
52	Incorrect	9 ms	2516 KB	Output isn't correct
53	Correct	71 ms	2532 KB	Output is correct
54	Incorrect	11 ms	2772 KB	Output isn't correct
55	Incorrect	11 ms	2796 KB	Output isn't correct
56	Correct	66 ms	2800 KB	Output is correct
57	Incorrect	12 ms	3148 KB	Output isn't correct
58	Incorrect	12 ms	3148 KB	Output isn't correct
59	Correct	92 ms	3244 KB	Output is correct
60	Incorrect	14 ms	3540 KB	Output isn't correct
61	Incorrect	13 ms	3536 KB	Output isn't correct
62	Correct	86 ms	3640 KB	Output is correct
63	Correct	80 ms	3632 KB	Output is correct
64	Incorrect	146 ms	3636 KB	Output isn't correct
65	Incorrect	129 ms	3536 KB	Output isn't correct
66	Incorrect	121 ms	3664 KB	Output isn't correct
67	Correct	75 ms	3652 KB	Output is correct
68	Correct	43 ms	3648 KB	Output is correct
69	Correct	37 ms	3536 KB	Output is correct
70	Correct	45 ms	3540 KB	Output is correct
71	Correct	33 ms	3560 KB	Output is correct
72	Incorrect	40 ms	3552 KB	Output isn't correct
73	Correct	45 ms	3796 KB	Output is correct
74	Incorrect	67 ms	3796 KB	Output isn't correct
75	Incorrect	61 ms	3796 KB	Output isn't correct
76	Correct	60 ms	3796 KB	Output is correct
77	Incorrect	86 ms	3788 KB	Output isn't correct
78	Correct	63 ms	3668 KB	Output is correct
79	Incorrect	107 ms	3764 KB	Output isn't correct
80	Correct	66 ms	3768 KB	Output is correct
81	Correct	77 ms	3668 KB	Output is correct
82	Incorrect	67 ms	3668 KB	Output isn't correct
83	Correct	64 ms	3728 KB	Output is correct
84	Incorrect	71 ms	3728 KB	Output isn't correct
85	Correct	70 ms	3728 KB	Output is correct
86	Correct	72 ms	3724 KB	Output is correct
87	Correct	62 ms	3728 KB	Output is correct
88	Correct	67 ms	3680 KB	Output is correct
89	Correct	72 ms	3672 KB	Output is correct
90	Correct	74 ms	3668 KB	Output is correct
91	Correct	69 ms	3680 KB	Output is correct
92	Correct	73 ms	3672 KB	Output is correct