답안 #802808

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
802808	2023-08-02T14:43:51 Z	_VIBE	Mecho (IOI09_mecho)	C++17	39 / 100	156 ms	3916 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=2*g[x][y];
    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

39.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 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	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	75 ms	3640 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	212 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	0 ms	340 KB	Output isn't correct
16	Correct	0 ms	212 KB	Output is correct
17	Incorrect	0 ms	212 KB	Output isn't correct
18	Correct	0 ms	340 KB	Output is 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	1 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	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	340 KB	Output isn't correct
33	Incorrect	3 ms	980 KB	Output isn't correct
34	Incorrect	3 ms	980 KB	Output isn't correct
35	Correct	17 ms	980 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	23 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	29 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	43 ms	1620 KB	Output is correct
45	Incorrect	7 ms	1876 KB	Output isn't correct
46	Incorrect	7 ms	1916 KB	Output isn't correct
47	Correct	46 ms	1924 KB	Output is correct
48	Incorrect	8 ms	2132 KB	Output isn't correct
49	Incorrect	8 ms	2132 KB	Output isn't correct
50	Correct	52 ms	2148 KB	Output is correct
51	Incorrect	9 ms	2456 KB	Output isn't correct
52	Incorrect	9 ms	2516 KB	Output isn't correct
53	Correct	60 ms	2544 KB	Output is correct
54	Incorrect	11 ms	2792 KB	Output isn't correct
55	Incorrect	11 ms	2796 KB	Output isn't correct
56	Correct	71 ms	2880 KB	Output is correct
57	Incorrect	12 ms	3156 KB	Output isn't correct
58	Incorrect	12 ms	3156 KB	Output isn't correct
59	Correct	91 ms	3272 KB	Output is correct
60	Incorrect	14 ms	3528 KB	Output isn't correct
61	Incorrect	13 ms	3528 KB	Output isn't correct
62	Correct	93 ms	3648 KB	Output is correct
63	Correct	84 ms	3532 KB	Output is correct
64	Incorrect	154 ms	3524 KB	Output isn't correct
65	Incorrect	156 ms	3524 KB	Output isn't correct
66	Incorrect	136 ms	3540 KB	Output isn't correct
67	Correct	88 ms	3540 KB	Output is correct
68	Correct	43 ms	3640 KB	Output is correct
69	Correct	41 ms	3640 KB	Output is correct
70	Correct	31 ms	3560 KB	Output is correct
71	Correct	36 ms	3560 KB	Output is correct
72	Incorrect	30 ms	3540 KB	Output isn't correct
73	Correct	30 ms	3796 KB	Output is correct
74	Incorrect	74 ms	3916 KB	Output isn't correct
75	Correct	62 ms	3796 KB	Output is correct
76	Correct	59 ms	3796 KB	Output is correct
77	Incorrect	61 ms	3808 KB	Output isn't correct
78	Correct	68 ms	3668 KB	Output is correct
79	Incorrect	58 ms	3668 KB	Output isn't correct
80	Correct	65 ms	3780 KB	Output is correct
81	Correct	62 ms	3764 KB	Output is correct
82	Correct	55 ms	3764 KB	Output is correct
83	Correct	69 ms	3724 KB	Output is correct
84	Correct	62 ms	3732 KB	Output is correct
85	Correct	73 ms	3664 KB	Output is correct
86	Correct	70 ms	3724 KB	Output is correct
87	Correct	71 ms	3740 KB	Output is correct
88	Correct	72 ms	3664 KB	Output is correct
89	Correct	72 ms	3668 KB	Output is correct
90	Correct	75 ms	3676 KB	Output is correct
91	Correct	74 ms	3668 KB	Output is correct
92	Correct	81 ms	3668 KB	Output is correct