답안 #802772

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
802772	2023-08-02T14:15:44 Z	_VIBE	Mecho (IOI09_mecho)	C++17	53 / 100	171 ms	4436 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=3*n;
    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

53.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	1 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	93 ms	4276 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	336 KB	Output is correct
12	Incorrect	1 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	Incorrect	1 ms	340 KB	Output isn't 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	1 ms	340 KB	Output isn't correct
21	Incorrect	0 ms	340 KB	Output isn't correct
22	Incorrect	1 ms	332 KB	Output isn't correct
23	Incorrect	1 ms	340 KB	Output isn't correct
24	Incorrect	1 ms	332 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	1 ms	340 KB	Output isn't correct
31	Incorrect	1 ms	340 KB	Output isn't correct
32	Incorrect	1 ms	336 KB	Output isn't correct
33	Incorrect	3 ms	980 KB	Output isn't correct
34	Incorrect	3 ms	1108 KB	Output isn't correct
35	Correct	19 ms	1080 KB	Output is correct
36	Incorrect	4 ms	1156 KB	Output isn't correct
37	Incorrect	4 ms	1316 KB	Output isn't correct
38	Correct	25 ms	1352 KB	Output is correct
39	Incorrect	5 ms	1364 KB	Output isn't correct
40	Incorrect	5 ms	1556 KB	Output isn't correct
41	Correct	33 ms	1492 KB	Output is correct
42	Incorrect	8 ms	1620 KB	Output isn't correct
43	Incorrect	6 ms	1836 KB	Output isn't correct
44	Correct	44 ms	1968 KB	Output is correct
45	Incorrect	7 ms	1848 KB	Output isn't correct
46	Incorrect	7 ms	2096 KB	Output isn't correct
47	Correct	51 ms	2132 KB	Output is correct
48	Incorrect	8 ms	2144 KB	Output isn't correct
49	Incorrect	9 ms	2516 KB	Output isn't correct
50	Correct	64 ms	2516 KB	Output is correct
51	Incorrect	9 ms	2516 KB	Output isn't correct
52	Incorrect	10 ms	2952 KB	Output isn't correct
53	Correct	75 ms	2948 KB	Output is correct
54	Incorrect	11 ms	2772 KB	Output isn't correct
55	Incorrect	17 ms	3284 KB	Output isn't correct
56	Correct	105 ms	3352 KB	Output is correct
57	Incorrect	14 ms	3156 KB	Output isn't correct
58	Incorrect	13 ms	3768 KB	Output isn't correct
59	Correct	101 ms	3792 KB	Output is correct
60	Incorrect	16 ms	3540 KB	Output isn't correct
61	Incorrect	15 ms	4160 KB	Output isn't correct
62	Correct	113 ms	4168 KB	Output is correct
63	Correct	101 ms	4284 KB	Output is correct
64	Correct	162 ms	4160 KB	Output is correct
65	Correct	171 ms	4264 KB	Output is correct
66	Correct	116 ms	4156 KB	Output is correct
67	Correct	104 ms	4264 KB	Output is correct
68	Correct	43 ms	4180 KB	Output is correct
69	Correct	35 ms	4180 KB	Output is correct
70	Correct	35 ms	4180 KB	Output is correct
71	Correct	38 ms	4288 KB	Output is correct
72	Correct	29 ms	4184 KB	Output is correct
73	Correct	29 ms	4436 KB	Output is correct
74	Correct	60 ms	4412 KB	Output is correct
75	Correct	68 ms	4360 KB	Output is correct
76	Correct	68 ms	4436 KB	Output is correct
77	Correct	59 ms	4408 KB	Output is correct
78	Correct	77 ms	4396 KB	Output is correct
79	Correct	49 ms	4308 KB	Output is correct
80	Correct	58 ms	4388 KB	Output is correct
81	Correct	76 ms	4408 KB	Output is correct
82	Correct	58 ms	4308 KB	Output is correct
83	Correct	76 ms	4308 KB	Output is correct
84	Correct	73 ms	4284 KB	Output is correct
85	Correct	71 ms	4356 KB	Output is correct
86	Correct	73 ms	4308 KB	Output is correct
87	Correct	85 ms	4356 KB	Output is correct
88	Correct	80 ms	4308 KB	Output is correct
89	Correct	79 ms	4308 KB	Output is correct
90	Correct	82 ms	4300 KB	Output is correct
91	Correct	91 ms	4304 KB	Output is correct
92	Correct	83 ms	4300 KB	Output is correct