답안 #802804

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
802804	2023-08-02T14:42:26 Z	_VIBE	Mecho (IOI09_mecho)	C++17	33 / 100	141 ms	3800 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]+2;
    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	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	70 ms	3628 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	1 ms	212 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	340 KB	Output isn't correct
16	Correct	0 ms	340 KB	Output is correct
17	Incorrect	0 ms	212 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	1 ms	340 KB	Output isn't correct
21	Incorrect	1 ms	340 KB	Output isn't correct
22	Incorrect	1 ms	340 KB	Output isn't correct
23	Incorrect	1 ms	340 KB	Output isn't correct
24	Incorrect	1 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	1 ms	340 KB	Output isn't correct
29	Incorrect	1 ms	340 KB	Output isn't correct
30	Incorrect	0 ms	340 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	1004 KB	Output is correct
36	Incorrect	4 ms	1108 KB	Output isn't correct
37	Incorrect	4 ms	1108 KB	Output isn't correct
38	Correct	22 ms	1200 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	26 ms	1364 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	1644 KB	Output is correct
45	Incorrect	8 ms	1876 KB	Output isn't correct
46	Incorrect	7 ms	1876 KB	Output isn't correct
47	Correct	40 ms	1860 KB	Output is correct
48	Incorrect	8 ms	2144 KB	Output isn't correct
49	Incorrect	9 ms	2144 KB	Output isn't correct
50	Correct	47 ms	2132 KB	Output is correct
51	Incorrect	9 ms	2448 KB	Output isn't correct
52	Incorrect	9 ms	2516 KB	Output isn't correct
53	Correct	56 ms	2532 KB	Output is correct
54	Incorrect	11 ms	2772 KB	Output isn't correct
55	Incorrect	11 ms	2792 KB	Output isn't correct
56	Correct	67 ms	2772 KB	Output is correct
57	Incorrect	12 ms	3156 KB	Output isn't correct
58	Incorrect	12 ms	3140 KB	Output isn't correct
59	Correct	74 ms	3148 KB	Output is correct
60	Incorrect	14 ms	3532 KB	Output isn't correct
61	Incorrect	13 ms	3532 KB	Output isn't correct
62	Correct	86 ms	3648 KB	Output is correct
63	Correct	74 ms	3528 KB	Output is correct
64	Incorrect	141 ms	3640 KB	Output isn't correct
65	Incorrect	134 ms	3524 KB	Output isn't correct
66	Incorrect	117 ms	3524 KB	Output isn't correct
67	Correct	76 ms	3640 KB	Output is correct
68	Correct	50 ms	3636 KB	Output is correct
69	Correct	42 ms	3540 KB	Output is correct
70	Correct	38 ms	3564 KB	Output is correct
71	Correct	33 ms	3564 KB	Output is correct
72	Incorrect	29 ms	3564 KB	Output isn't correct
73	Correct	29 ms	3788 KB	Output is correct
74	Incorrect	68 ms	3800 KB	Output isn't correct
75	Incorrect	61 ms	3796 KB	Output isn't correct
76	Correct	55 ms	3796 KB	Output is correct
77	Incorrect	73 ms	3796 KB	Output isn't correct
78	Correct	66 ms	3776 KB	Output is correct
79	Incorrect	69 ms	3772 KB	Output isn't correct
80	Incorrect	59 ms	3764 KB	Output isn't correct
81	Correct	57 ms	3768 KB	Output is correct
82	Incorrect	63 ms	3768 KB	Output isn't correct
83	Correct	63 ms	3668 KB	Output is correct
84	Incorrect	68 ms	3724 KB	Output isn't correct
85	Correct	69 ms	3668 KB	Output is correct
86	Correct	82 ms	3724 KB	Output is correct
87	Correct	67 ms	3720 KB	Output is correct
88	Correct	67 ms	3676 KB	Output is correct
89	Correct	74 ms	3668 KB	Output is correct
90	Correct	77 ms	3668 KB	Output is correct
91	Correct	68 ms	3668 KB	Output is correct
92	Correct	80 ms	3788 KB	Output is correct