Submission #236178

# Submission time Handle Problem Language Result Execution time Memory
236178 2020-05-31T12:50:03 Z nicolaalexandra Mecho (IOI09_mecho) C++14
37 / 100
246 ms 8696 KB
#include <bits/stdc++.h>
#define DIM 810
using namespace std;

char s[DIM];
int a[DIM][DIM],b[DIM][DIM],dist[DIM][DIM],f[DIM];
deque <pair<int,int> > c,aux,d;
int di[] = {-1,1,0,0};
int dj[] = {0,0,-1,1};
int n,nr,i,j,xstart,ystart,xfin,yfin;
inline int inmat (int i, int j){
    if (i >= 1 && j >= 1 && i <= n && j <= n)
        return 1;
    return 0;
}
int verif (int val){

    /// mai intai vad cat se extind albinele dupa val secunde
    c.clear();
    memset (f,0,sizeof f);
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++){
            b[i][j] = a[i][j];
            if (a[i][j] == 1)
                c.push_back(make_pair(i,j));
        }

    for (i=1;i<=val;i++){
        aux.clear();
        for (auto it : c){
            int ic = it.first, jc = it.second;
            for (int dir=0;dir<=3;dir++){
                int iv = ic + di[dir];
                int jv = jc + dj[dir];
                if (inmat (iv,jv) && b[iv][jv] == 0){
                    aux.push_back(make_pair(iv,jv));
                    b[iv][jv] = 1;
                }}}
        c = aux;
        f[i] = 1;
    }

    if (b[xstart][ystart])
        return 0;

    /// d - lista cu toate locurile in care pot sa ajung pana la secunda asta
    memset (dist,0,sizeof dist);
    d.clear();
    d.push_back(make_pair(xstart,ystart));
    dist[xstart][ystart] = 1;

    while (!d.empty()){
        int ic = d.front().first;
        int jc = d.front().second;
        d.pop_front();

        if (dist[ic][jc] % nr == 0 && !f[dist[ic][jc] / nr + val]){
            /// inseamna ca a mai trecut un minut si trb sa avansez cu albinele
            f[dist[ic][jc] / nr + val] = 1;
            aux.clear();
            for (auto it : c){
                int i = it.first, j = it.second;
                for (int dir=0;dir<=3;dir++){
                    int iv = i + di[dir];
                    int jv = j + dj[dir];
                    if (inmat(iv,jv) && b[iv][jv] == 0){
                        aux.push_back(make_pair(iv,jv));
                        b[iv][jv] = 1;
                    }}}
            c = aux;
        }

        for (int dir=0;dir<=3;dir++){
            int iv = ic + di[dir];
            int jv = jc + dj[dir];
            if (inmat (iv,jv) && (b[iv][jv] == 0 || b[iv][jv] == 3) && !dist[iv][jv]){
                if (iv == xfin && jv == yfin) /// am reusit sa ajung
                    return 1;

                dist[iv][jv] = 1 + dist[ic][jc];
                d.push_back(make_pair(iv,jv));
            }}}

    return 0;

}


int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>nr;
    for (i=1;i<=n;i++){
        cin>>s+1;
        for (j=1;j<=n;j++){
            if (s[j] == 'T')
                a[i][j] = 2;
            if (s[j] == 'M'){
                xstart = i, ystart = j;
                //a[i][j] = 4;
            }
            if (s[j] == 'D'){
                xfin = i, yfin = j;
                a[i][j] = 3;
            }
            if (s[j] == 'H')
                a[i][j] = 1;
        }
    }
    /*for (i=1;i<=n;i++,cout<<endl)
        for (j=1;j<=n;j++)
            cout<<a[i][j]<<" ";
*/
    int st = 0, dr = n, sol = 0;
    while (st <= dr){
        int mid = (st+dr)>>1;
        if (verif (mid)){
            sol = mid;
            st = mid+1;
        } else dr = mid-1;
    }

    cout<<sol;

    return 0;
}

Compilation message

mecho.cpp: In function 'int main()':
mecho.cpp:96:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         cin>>s+1;
              ~^~
# Verdict Execution time Memory Grader output
1 Correct 6 ms 2944 KB Output is correct
2 Correct 6 ms 2944 KB Output is correct
3 Correct 6 ms 2944 KB Output is correct
4 Correct 6 ms 2944 KB Output is correct
5 Correct 6 ms 2944 KB Output is correct
6 Correct 6 ms 2944 KB Output is correct
7 Correct 203 ms 7288 KB Output is correct
8 Incorrect 6 ms 3072 KB Output isn't correct
9 Correct 6 ms 2944 KB Output is correct
10 Correct 6 ms 2944 KB Output is correct
11 Correct 6 ms 2944 KB Output is correct
12 Incorrect 7 ms 3328 KB Output isn't correct
13 Correct 6 ms 3200 KB Output is correct
14 Incorrect 7 ms 3328 KB Output isn't correct
15 Incorrect 6 ms 3072 KB Output isn't correct
16 Incorrect 6 ms 3072 KB Output isn't correct
17 Incorrect 6 ms 3072 KB Output isn't correct
18 Incorrect 6 ms 3072 KB Output isn't correct
19 Incorrect 6 ms 3072 KB Output isn't correct
20 Incorrect 6 ms 3072 KB Output isn't correct
21 Incorrect 6 ms 3072 KB Output isn't correct
22 Incorrect 6 ms 3200 KB Output isn't correct
23 Incorrect 6 ms 3200 KB Output isn't correct
24 Incorrect 6 ms 3200 KB Output isn't correct
25 Incorrect 7 ms 3200 KB Output isn't correct
26 Incorrect 7 ms 3328 KB Output isn't correct
27 Incorrect 7 ms 3200 KB Output isn't correct
28 Incorrect 7 ms 3328 KB Output isn't correct
29 Incorrect 7 ms 3248 KB Output isn't correct
30 Incorrect 7 ms 3328 KB Output isn't correct
31 Incorrect 7 ms 3328 KB Output isn't correct
32 Incorrect 7 ms 3328 KB Output isn't correct
33 Incorrect 17 ms 4992 KB Output isn't correct
34 Incorrect 18 ms 5120 KB Output isn't correct
35 Correct 31 ms 5120 KB Output is correct
36 Incorrect 21 ms 5248 KB Output isn't correct
37 Incorrect 21 ms 5504 KB Output isn't correct
38 Correct 40 ms 5504 KB Output is correct
39 Incorrect 25 ms 5632 KB Output isn't correct
40 Incorrect 25 ms 5760 KB Output isn't correct
41 Correct 50 ms 5760 KB Output is correct
42 Incorrect 29 ms 6016 KB Output isn't correct
43 Incorrect 29 ms 6016 KB Output isn't correct
44 Correct 62 ms 6016 KB Output is correct
45 Incorrect 35 ms 6392 KB Output isn't correct
46 Incorrect 35 ms 6400 KB Output isn't correct
47 Correct 70 ms 6400 KB Output is correct
48 Incorrect 40 ms 6656 KB Output isn't correct
49 Incorrect 41 ms 6784 KB Output isn't correct
50 Correct 82 ms 6904 KB Output is correct
51 Incorrect 45 ms 7160 KB Output isn't correct
52 Incorrect 47 ms 7040 KB Output isn't correct
53 Correct 101 ms 7032 KB Output is correct
54 Incorrect 51 ms 7296 KB Output isn't correct
55 Incorrect 51 ms 7288 KB Output isn't correct
56 Correct 115 ms 7416 KB Output is correct
57 Incorrect 57 ms 7680 KB Output isn't correct
58 Incorrect 58 ms 7672 KB Output isn't correct
59 Correct 135 ms 7680 KB Output is correct
60 Incorrect 64 ms 7936 KB Output isn't correct
61 Incorrect 65 ms 7928 KB Output isn't correct
62 Correct 160 ms 7928 KB Output is correct
63 Incorrect 220 ms 8032 KB Output isn't correct
64 Incorrect 246 ms 8064 KB Output isn't correct
65 Incorrect 221 ms 7928 KB Output isn't correct
66 Incorrect 233 ms 8056 KB Output isn't correct
67 Incorrect 194 ms 7928 KB Output isn't correct
68 Correct 192 ms 7968 KB Output is correct
69 Correct 142 ms 8056 KB Output is correct
70 Correct 157 ms 8056 KB Output is correct
71 Correct 162 ms 8084 KB Output is correct
72 Correct 201 ms 8056 KB Output is correct
73 Correct 148 ms 8696 KB Output is correct
74 Correct 201 ms 8572 KB Output is correct
75 Correct 195 ms 8568 KB Output is correct
76 Correct 215 ms 8568 KB Output is correct
77 Correct 189 ms 8568 KB Output is correct
78 Incorrect 194 ms 8568 KB Output isn't correct
79 Correct 207 ms 8568 KB Output is correct
80 Correct 193 ms 8440 KB Output is correct
81 Correct 215 ms 8696 KB Output is correct
82 Correct 205 ms 8440 KB Output is correct
83 Correct 207 ms 8568 KB Output is correct
84 Correct 208 ms 8440 KB Output is correct
85 Correct 213 ms 8440 KB Output is correct
86 Correct 213 ms 8440 KB Output is correct
87 Correct 211 ms 8440 KB Output is correct
88 Correct 210 ms 8312 KB Output is correct
89 Correct 204 ms 8440 KB Output is correct
90 Correct 209 ms 8440 KB Output is correct
91 Correct 204 ms 8312 KB Output is correct
92 Correct 216 ms 8312 KB Output is correct