Submission #313755

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
313755	2020-10-16T23:45:07 Z	Massiosare	Mecho (IOI09_mecho)	C++14	6 / 100	245 ms	11716 KB

mecho

#include <iostream>
#include <queue>

#define MAX 805

using namespace std;

struct coords{
    int fil;
    int col;
    int nivel;
    int temporal;
};

int best;
int maxpro;
coords pro,start;
int n,steps;
char mat[MAX][MAX];
bool visitados[MAX][MAX];
int valores[MAX][MAX];
queue <coords> q,q2;

void add(coords temp){
    coords temp2=temp;
    temp2.nivel++;
    //col+
    temp2.col++;
    q.push(temp2);
    temp2.col--;
    //fil+
    temp2.fil++;
    q.push(temp2);
    temp2.fil--;
    //col-
    temp2.col--;
    q.push(temp2);
    temp2.col++;
    //fil-
    temp2.fil--;
    q.push(temp2);
    temp2.fil++;
    return;
}

void add2(coords temp){
    coords temp2=temp;
    temp2.temporal++;
    if(temp2.temporal%steps==0){
        temp2.nivel++;
    }
    //col+
    temp2.col++;
    q2.push(temp2);
    temp2.col--;
    //fil+
    temp2.fil++;
    q2.push(temp2);
    temp2.fil--;
    //col-
    temp2.col--;
    q2.push(temp2);
    temp2.col++;
    //fil-
    temp2.fil--;
    q2.push(temp2);
    temp2.fil++;
    return;
}

bool busca2(){
    while(!q2.empty()){
        coords temp=q2.front();
        q2.pop();
        if(temp.col<1||temp.col>n||temp.fil>n||temp.fil<1){
            continue;
        }
        if(visitados[temp.fil][temp.col]==1||mat[temp.fil][temp.col]=='T'){
            continue;
        }
        else {
            visitados[temp.fil][temp.col]=1;
        }
        if(valores[temp.fil][temp.col]<=temp.nivel){
            continue;
        }
        if(mat[temp.fil][temp.col]=='D'){
            if(valores[temp.fil][temp.col]<=temp.nivel){
                return 0;
            }
            return 1;
        }
        add2(temp);
    }
    return 0;
}

void binaria(int ini,int fin){
    while(ini<=fin){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                visitados[i][j]=0;
            }
        }
        while(!q2.empty()){
            q.pop();
        }
        int mid=(ini+fin)/2;
        start.nivel=mid;
        q2.push(start);
        bool x=busca2();
        if(x==1){
            best=mid;
            ini=mid+1;
        }
        else {
            fin=mid-1;
        }
    }
    cout << best;
}

void busca(){
    while(!q.empty()){
        coords temp=q.front();
        q.pop();
        if(temp.col<1||temp.col>n||temp.fil>n||temp.fil<1){
            continue;
        }
        if(visitados[temp.fil][temp.col]==0){
            valores[temp.fil][temp.col]=temp.nivel;
            visitados[temp.fil][temp.col]=1;
        }
        else {
            continue;
        }
        if(mat[temp.fil][temp.col]=='M'){
            maxpro=valores[temp.fil][temp.col];
        }
        add(temp);
    }
    return;
}

int main()
{
    cin >> n >> steps;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin >> mat[i][j];
            if(mat[i][j]=='H'){
                pro.fil=i;
                pro.col=j;
                q.push(pro);
            }
            if(mat[i][j]=='M'){
                start.fil=i;
                start.col=j;
                start.nivel=0;
            }
        }
    }
    busca();
    binaria(1,maxpro);
    return 0;
}

Subtask #1

6.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Incorrect	0 ms	384 KB	Output isn't correct
3	Runtime error	1 ms	512 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
4	Incorrect	0 ms	384 KB	Output isn't correct
5	Correct	1 ms	384 KB	Output is correct
6	Incorrect	1 ms	384 KB	Output isn't correct
7	Runtime error	160 ms	9972 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Incorrect	1 ms	384 KB	Output isn't correct
9	Runtime error	1 ms	640 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
10	Runtime error	1 ms	640 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
11	Runtime error	1 ms	640 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
12	Incorrect	1 ms	640 KB	Output isn't correct
13	Correct	1 ms	640 KB	Output is correct
14	Incorrect	2 ms	640 KB	Output isn't correct
15	Runtime error	3 ms	768 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
16	Runtime error	3 ms	768 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
17	Runtime error	4 ms	896 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
18	Runtime error	4 ms	896 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
19	Runtime error	3 ms	896 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
20	Runtime error	4 ms	896 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
21	Runtime error	4 ms	1024 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
22	Runtime error	2 ms	896 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
23	Runtime error	4 ms	1152 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
24	Runtime error	2 ms	896 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
25	Runtime error	4 ms	1280 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
26	Runtime error	4 ms	1280 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
27	Runtime error	4 ms	1280 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
28	Runtime error	4 ms	1280 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
29	Runtime error	4 ms	1280 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
30	Runtime error	4 ms	1280 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
31	Runtime error	5 ms	1396 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
32	Runtime error	5 ms	1408 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
33	Runtime error	22 ms	3968 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
34	Runtime error	22 ms	4096 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
35	Runtime error	46 ms	4088 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
36	Runtime error	27 ms	4472 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
37	Runtime error	28 ms	4480 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
38	Runtime error	59 ms	4624 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
39	Runtime error	33 ms	4984 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
40	Runtime error	33 ms	5112 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
41	Runtime error	80 ms	5196 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
42	Runtime error	39 ms	5496 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
43	Runtime error	39 ms	5500 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
44	Runtime error	89 ms	5496 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
45	Runtime error	48 ms	6136 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
46	Runtime error	56 ms	6032 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
47	Runtime error	110 ms	6116 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
48	Runtime error	54 ms	6392 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
49	Runtime error	54 ms	6392 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
50	Runtime error	131 ms	6520 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
51	Runtime error	63 ms	7032 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
52	Runtime error	61 ms	6904 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
53	Runtime error	162 ms	7032 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
54	Runtime error	71 ms	7416 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
55	Runtime error	72 ms	7416 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
56	Runtime error	190 ms	7672 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
57	Runtime error	80 ms	7928 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
58	Runtime error	85 ms	8056 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
59	Runtime error	219 ms	8120 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
60	Runtime error	94 ms	8440 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
61	Runtime error	91 ms	8440 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
62	Runtime error	245 ms	8484 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
63	Correct	94 ms	4344 KB	Output is correct
64	Runtime error	113 ms	8440 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
65	Incorrect	221 ms	4216 KB	Output isn't correct
66	Incorrect	89 ms	4472 KB	Output isn't correct
67	Incorrect	120 ms	4216 KB	Output isn't correct
68	Correct	104 ms	5368 KB	Output is correct
69	Incorrect	121 ms	5372 KB	Output isn't correct
70	Incorrect	105 ms	5496 KB	Output isn't correct
71	Incorrect	103 ms	5368 KB	Output isn't correct
72	Runtime error	113 ms	10056 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
73	Runtime error	121 ms	11536 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
74	Runtime error	125 ms	11664 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
75	Runtime error	126 ms	11532 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
76	Runtime error	133 ms	11616 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
77	Runtime error	129 ms	11532 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
78	Incorrect	186 ms	5708 KB	Output isn't correct
79	Runtime error	119 ms	11468 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
80	Runtime error	125 ms	11336 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
81	Runtime error	143 ms	11716 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
82	Runtime error	117 ms	11468 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
83	Correct	189 ms	5668 KB	Output is correct
84	Runtime error	128 ms	11548 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
85	Runtime error	129 ms	11680 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
86	Runtime error	151 ms	11552 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
87	Runtime error	130 ms	11552 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
88	Correct	191 ms	4964 KB	Output is correct
89	Runtime error	136 ms	10088 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
90	Runtime error	162 ms	10216 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
91	Runtime error	147 ms	10084 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
92	Runtime error	169 ms	10084 KB	Execution killed with signal 11 (could be triggered by violating memory limits)