oj.uz

Submission #480600

# Submission time Handle Problem Language Result Execution time Memory
480600 2021-10-17T10:45:00 Z EntropyX Mecho (IOI09_mecho) C++17
12 / 100
 202 ms 12176 KB 
#include<bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0);cin.tie(0);

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define iiordered_set tree<pll, null_type,less<pll>, rb_tree_tag,tree_order_statistics_node_update>

using namespace std;

//Bit Functions
#define gcd __gcd
#define lsb __builtin_ffs
#define ldz __builtin_clz
#define tlz __builtin_ctz
#define stc __builtin_popcount
#define prtb(n) cout << bitset<20>(n) << "\n";

//Debugging
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
#define what_is(x) cerr << #x << " is " << x << endl;
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cerr << *it << " = " << a << endl;
    err(++it, args...);
}

//STL Declarations
#define vi vector<int>
#define vvi vector<vi>
#define vl vector<long long int>
#define vvl vector<vl>
#define vb vector<bool>
#define pii pair<int,int>
#define fr first
#define sc second
#define u_s unordered_set
#define ump unordered_map
#define ins insert
#define p_q(x) priority_queue<x>

//STL Functions
#define mt make_tuple
#define eb emplace_back
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define muq make_unique
#define all(x) x.begin(),x.end()
#define rot(vec,k) rotate(vec.begin(), vec.begin() + k, vec.end());
#define bs(vec,key) binary_search(all(vec), key)
#define parti(vec,p) partition_point(all(vec), p) - vec.begin()
#define srt(cnt) sort(all(cnt))
#define lb(cnt,x) lower_bound(all(cnt),x)
#define ub(cnt,x) upper_bound(all(cnt),x)
#define mxm(cnt) *max_element(all(cnt))
#define mnm(cnt) *min_element(all(cnt))
#define mxmptr(cnt) max_element(all(cnt))
#define mnmptr(cnt) min_element(all(cnt))
#define rev(cnt) reverse(all(cnt))
#define accum(cnt) accumulate(all(cnt),0)
#define look(cnt) for(auto c:cnt) cout<<c<<" "; cout<<"\n";
#define pre(x,cont) find(all(cont),x)!=cont.end()
#define pb push_back

//Input Functions
template<class T> istream& operator >> (istream &is , vector<T> &v) { for(T &a : v) is >> a; return is; }
template<class T> ostream& operator << (ostream &os , const vector<T> &v) { for(const T &t : v) os << t<<" "; return os << endl; }
template<class T, class U> ostream& operator << (ostream &os , const pair<T, U> &v) { return os << v.first << " " << v.second ; }

typedef long long int ll;
ll mod = 10000000007;

//Generalised Sum Function
int sum() { return 0; }
template<typename T, typename... Args>
T sum(T a, Args... args) { return a + sum(args...); }

vector<int> seive(int N){
    vector<bool> visited(N+1,false);
    vi pr;
    for(int i=2;i<=N;i++){
        if(!visited[i]){
            int j = i;
            pr.pb(j);
            while(j<=N){visited[j] = true;j+=i;}}}
    return pr;
}
ll ceil(ll a,ll b){
    if(b<0)a=-a,b=-b;
    if(a>=0)return (a+b-1)/b;
    return a/b;
}
long long bpow(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}
ll inverse(ll a,ll m=mod)
{
    return bpow(a,m-2,m);
}
vvl matmul(const vvl &a,const vvl &b,ll M=mod)
{
    int n=a.size(),m=a[0].size(),l=b[0].size();
    assert(m==b.size());
    vvl c(n,vl(l,0));
    rep(i,0,n)
        rep(j,0,l)
            rep(k,0,m)
            {
                c[i][j]=(c[i][j]+a[i][k]*b[k][j])%M;
            }
    return c;
}
vvl matpow(vvl a,ll p,ll M=mod)
{
    assert(a.size()==a[0].size());
    int n=a.size();
    vvl res(n,vl(n,0));
    rep(i,0,n)   res[i][i]=1;
    while(p>0)
    {
        if(p&1) res=matmul(res,a,M);
        a=matmul(a,a,M);
        p>>=1;
    }
    return res;
}

const ll COMBINATION_SIZE = 300005;
const ll MOD = 1e9+7;

struct Combination {
    long long fac[COMBINATION_SIZE], inv[COMBINATION_SIZE];
    bool built = 0;
    void build(){
        assert(MOD >= COMBINATION_SIZE);
        fac[0] = 1;
        for(int i = 1; i < COMBINATION_SIZE; i++) {
            fac[i] = fac[i - 1] * i % MOD;
        }
        inv[COMBINATION_SIZE - 1] = inverse(fac[COMBINATION_SIZE - 1], MOD);
        for(int i = COMBINATION_SIZE - 2; i >= 0; i--) {
            inv[i] = inv[i + 1] * (i + 1) % MOD;
        }
    }
    long long C(int x, int y){
        if(y < 0 || y > x) {
            return 0;
        }
        if(!built) {
            built = 1;
            build();
        }
        return fac[x] * inv[y] % MOD * inv[x-y] % MOD;
    }
} comb;

void setIO(string s) { // the argument is the filename without the extension
    freopen((s+".in").c_str(),"r",stdin);
    freopen((s+".out").c_str(),"w",stdout);
}

int main(){ _
    int n,s;cin >> n >> s;
    vector<string> vec(n);
    rep(i,0,n)
        cin >> vec[i];
    auto valid = [&](int x,int y){
        if(x<0 || y<0 || x>=n || y>=n)
            return false;
        return true;
    };
    vector<pii> dirs = {{+1,0},{-1,0},{0,+1},{0,-1}};
    pii start;pii end;
    queue<pii> q;
    vector<vi> d(n,vi(n,-1));
    rep(i,0,n){
        rep(j,0,n){
            if(vec[i][j] == 'H'){
                q.push({i,j});
                d[i][j] = 0;
            }
            else if(vec[i][j] == 'M'){
                start = {i,j};
            }
            else if(vec[i][j] == 'D'){
                end = {i,j};
            }
        }
    }
    // The bee action is finished!
    while(!q.empty()){
        auto p = q.front();q.pop();
        int x = p.fr;int y = p.sc;
        int dd = d[x][y];
        for(auto c:dirs){
            int X = x+c.fr;
            int Y = y+c.sc;
            if(valid(X,Y) && (d[X][Y] == -1) && vec[X][Y]!='T' && vec[X][Y]!='D'){
                q.push({X,Y});
                d[X][Y] = dd+s;
            }
        }
    }
    auto check = [&](int start_time){
        if(d[start.fr][start.sc] <= start_time)
            return false;
        queue<pii> q2;
        vector<vi> d2(n,vi(n,-1));
        q2.push(start);
        d2[start.fr][start.sc] = start_time;
        while(!q2.empty()){
            auto p = q2.front();
            q2.pop();
            int x = p.fr;
            int y = p.sc;
            int dd = d2[x][y];
            int chk = dd + 1;
            for(auto c:dirs){
                int X = x + c.fr;
                int Y = y + c.sc;
                if(vec[X][Y] == 'D'){
                    d2[X][Y] = chk;
                    q2.push({X,Y});
                }
                else if(valid(X,Y) && d2[X][Y] == -1 && vec[X][Y] != 'T' && chk < d[X][Y]){
                    d2[X][Y] = chk;
                    q2.push({X,Y});
                }
            }
        }
        return d2[end.fr][end.sc]!=-1;
    };
    if(!check(0)){
        cout << "-1\n";
    }
    else{
        int r = n*n*2;
        int l = 0;
        while(r-l>1){
            int mid = (l+r)/2;
            if(check(mid)){
                l = mid;
            }
            else{
                r = mid;
            }
        }
        l = (l/s);
        cout << l << "\n";
    }
    return 0;
}

Compilation message

In file included from /usr/include/c++/10/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp:45,
                 from /usr/include/c++/10/ext/pb_ds/detail/container_base_dispatch.hpp:90,
                 from /usr/include/c++/10/ext/pb_ds/assoc_container.hpp:48,
                 from mecho.cpp:4:
mecho.cpp: In function 'std::vector<std::vector<long long int> > matmul(const std::vector<std::vector<long long int> >&, const std::vector<std::vector<long long int> >&, ll)':
mecho.cpp:111:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |     assert(m==b.size());
      |            ~^~~~~~~~~~
mecho.cpp: In function 'void setIO(std::string)':
mecho.cpp:166:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |     freopen((s+".in").c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:167:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |     freopen((s+".out").c_str(),"w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 11
2 Runtime error 1 ms 460 KB Execution killed with signal 11
3 Runtime error 1 ms 460 KB Execution killed with signal 11
4 Runtime error 1 ms 460 KB Execution killed with signal 11
5 Runtime error 1 ms 460 KB Execution killed with signal 11
6 Runtime error 1 ms 460 KB Execution killed with signal 11
7 Runtime error 26 ms 12108 KB Execution killed with signal 11
8 Runtime error 1 ms 460 KB Execution killed with signal 11
9 Runtime error 1 ms 460 KB Execution killed with signal 11
10 Runtime error 1 ms 460 KB Execution killed with signal 11
11 Runtime error 1 ms 460 KB Execution killed with signal 11
12 Runtime error 1 ms 460 KB Execution killed with signal 11
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Runtime error 1 ms 460 KB Execution killed with signal 11
16 Runtime error 1 ms 460 KB Execution killed with signal 11
17 Runtime error 1 ms 460 KB Execution killed with signal 11
18 Runtime error 1 ms 460 KB Execution killed with signal 11
19 Runtime error 1 ms 460 KB Execution killed with signal 11
20 Runtime error 1 ms 460 KB Execution killed with signal 11
21 Runtime error 1 ms 460 KB Execution killed with signal 11
22 Runtime error 1 ms 460 KB Execution killed with signal 11
23 Runtime error 1 ms 460 KB Execution killed with signal 11
24 Runtime error 1 ms 460 KB Execution killed with signal 11
25 Runtime error 1 ms 460 KB Execution killed with signal 11
26 Runtime error 2 ms 460 KB Execution killed with signal 11
27 Runtime error 1 ms 460 KB Execution killed with signal 11
28 Runtime error 2 ms 460 KB Execution killed with signal 11
29 Runtime error 1 ms 460 KB Execution killed with signal 11
30 Runtime error 1 ms 460 KB Execution killed with signal 11
31 Runtime error 1 ms 460 KB Execution killed with signal 11
32 Runtime error 1 ms 460 KB Execution killed with signal 11
33 Runtime error 4 ms 2636 KB Execution killed with signal 11
34 Runtime error 4 ms 2636 KB Execution killed with signal 11
35 Runtime error 6 ms 2724 KB Execution killed with signal 11
36 Runtime error 6 ms 3416 KB Execution killed with signal 11
37 Runtime error 5 ms 3404 KB Execution killed with signal 11
38 Runtime error 7 ms 3404 KB Execution killed with signal 11
39 Runtime error 7 ms 4176 KB Execution killed with signal 11
40 Runtime error 6 ms 4172 KB Execution killed with signal 11
41 Runtime error 8 ms 4172 KB Execution killed with signal 11
42 Runtime error 8 ms 5068 KB Execution killed with signal 11
43 Runtime error 11 ms 5196 KB Execution killed with signal 11
44 Runtime error 10 ms 5068 KB Execution killed with signal 11
45 Runtime error 9 ms 5964 KB Execution killed with signal 11
46 Runtime error 9 ms 5964 KB Execution killed with signal 11
47 Runtime error 13 ms 5964 KB Execution killed with signal 11
48 Runtime error 12 ms 7020 KB Execution killed with signal 11
49 Runtime error 12 ms 7020 KB Execution killed with signal 11
50 Runtime error 15 ms 6988 KB Execution killed with signal 11
51 Runtime error 14 ms 8140 KB Execution killed with signal 11
52 Runtime error 13 ms 8140 KB Execution killed with signal 11
53 Runtime error 18 ms 8112 KB Execution killed with signal 11
54 Runtime error 15 ms 9380 KB Execution killed with signal 11
55 Runtime error 16 ms 9464 KB Execution killed with signal 11
56 Runtime error 20 ms 9420 KB Execution killed with signal 11
57 Runtime error 16 ms 10700 KB Execution killed with signal 11
58 Runtime error 17 ms 10708 KB Execution killed with signal 11
59 Runtime error 28 ms 10640 KB Execution killed with signal 11
60 Runtime error 18 ms 12132 KB Execution killed with signal 11
61 Runtime error 20 ms 12124 KB Execution killed with signal 11
62 Runtime error 26 ms 12064 KB Execution killed with signal 11
63 Runtime error 32 ms 12124 KB Execution killed with signal 11
64 Runtime error 32 ms 12084 KB Execution killed with signal 11
65 Runtime error 40 ms 12124 KB Execution killed with signal 11
66 Runtime error 31 ms 12104 KB Execution killed with signal 11
67 Runtime error 32 ms 12100 KB Execution killed with signal 11
68 Runtime error 36 ms 12148 KB Execution killed with signal 11
69 Runtime error 34 ms 12100 KB Execution killed with signal 11
70 Runtime error 35 ms 12148 KB Execution killed with signal 11
71 Runtime error 37 ms 12116 KB Execution killed with signal 11
72 Runtime error 34 ms 12140 KB Execution killed with signal 11
73 Runtime error 41 ms 12132 KB Execution killed with signal 11
74 Runtime error 30 ms 12108 KB Execution killed with signal 11
75 Runtime error 27 ms 12144 KB Execution killed with signal 11
76 Runtime error 27 ms 12128 KB Execution killed with signal 11
77 Runtime error 31 ms 12144 KB Execution killed with signal 11
78 Correct 34 ms 6100 KB Output is correct
79 Correct 138 ms 6120 KB Output is correct
80 Correct 102 ms 6172 KB Output is correct
81 Correct 112 ms 6112 KB Output is correct
82 Correct 100 ms 6228 KB Output is correct
83 Runtime error 32 ms 12160 KB Execution killed with signal 11
84 Correct 182 ms 6160 KB Output is correct
85 Correct 119 ms 6156 KB Output is correct
86 Correct 160 ms 6112 KB Output is correct
87 Correct 141 ms 6096 KB Output is correct
88 Runtime error 29 ms 12176 KB Execution killed with signal 11
89 Correct 202 ms 6128 KB Output is correct
90 Correct 170 ms 6112 KB Output is correct
91 Correct 178 ms 6096 KB Output is correct
92 Correct 154 ms 6144 KB Output is correct