답안 #103694

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
103694	2019-04-02T04:46:29 Z	Badral	Mecho (IOI09_mecho)	C++17	10 / 100	1000 ms	66560 KB

mecho

#include<bits/stdc++.h>

using namespace std;

char a[1015][1015];
int bear[1105][1015];
int bee[1105][1015];
struct point{
    int x, y;
};
point mep(int a, int b) {point x; x.x = a; x.y = b; return x;}
int x = -1, y = -1;
int xxx = -1, yyy = -1;
    int n;
    int kk;
bool can(int k) {
    memset(bear, 0, sizeof bear);
    bear[x][y] = k*k;
    queue<point> q;
    q.push(mep(x, y));
    while(!q.empty()) {
        int x = q.front().x, y = q.front().y;
        q.pop();
        if( x < n && bear[x+1][y] == 0 && (a[x+1][y] == 'G' || a[x+1][y] == 'D') && bee[x+1][y] > (bear[x][y]+1)) {bear[x+1][y] = bear[x][y] + 1;q.push(mep(x+1, y));}
        if( x > 1 && bear[x-1][y] == 0 && (a[x-1][y] == 'G' || a[x-1][y] == 'D') && bee[x-1][y] > (bear[x][y]+1)) {bear[x-1][y] = bear[x][y] + 1;q.push(mep(x-1, y));}
        if( y < n && bear[x][y+1] == 0 && (a[x][y+1] == 'G' || a[x][y+1] == 'D') && bee[x][y+1] > (bear[x][y]+1)) {bear[x][y+1] = bear[x][y] + 1;q.push(mep(x, y+1));}
        if( y > 1 && bear[x][y-1] == 0 && (a[x][y-1] == 'G' || a[x][y-1] == 'D') && bee[x][y-1] > (bear[x][y]+1)) {bear[x][y-1] = bear[x][y] + 1;q.push(mep(x, y-1));}
    }
    return bear[xxx][yyy] != 0;  
}

int main() {
    cin >>n;
    cin >>kk;
    queue<point> p;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            bee[i][j] = INT_MAX; 
            cin >>a[i][j];
            if(a[i][j] == 'H') {p.push(mep(i, j));bee[i][j] = 0;}
            if(a[i][j] == 'M') {x = i; y = j;}
            if(a[i][j] == 'D') {xxx = i; yyy = j;}
        }
    }

    while(!p.empty()) {
        int x = p.front().x, y = p.front().y;
        p.pop();
        if(x < n && bee[x+1][y] > bee[x][y] + 1 && (a[x+1][y] != 'T' && a[x+1][y] != 'D')) {bee[x+1][y] = bee[x][y] + kk; p.push(mep(x+1, y));}
        if(x > 1 && bee[x-1][y] > bee[x][y] + 1 && (a[x-1][y] != 'T' && a[x-1][y] != 'D')) {bee[x-1][y] = bee[x][y] + kk; p.push(mep(x-1, y));}
        if(y < n && bee[x][y+1] > bee[x][y] + 1 && (a[x][y+1] != 'T' && a[x][y+1] != 'D')) {bee[x][y+1] = bee[x][y] + kk; p.push(mep(x, y+1));}
        if(y > 1 && bee[x][y-1] > bee[x][y] + 1 && (a[x][y-1] != 'T' && a[x][y-1] != 'D')) {bee[x][y-1] = bee[x][y] + kk; p.push(mep(x, y-1));}
    }
    for(int i = 1; i <= n*n; i++) {
        if(can(i))
        return cout<<i, 0;
    }
    int k = 0, mm = n * n;
    for(int i = mm/2; i >= 1; i /= 2) 
        while(i + k <= mm && can(i+k)) 
            k += i;
    cout<<(k == 0?-1:k);
}

Subtask #1

10.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	4736 KB	Output is correct
2	Correct	6 ms	4736 KB	Output is correct
3	Incorrect	6 ms	4736 KB	Output isn't correct
4	Incorrect	6 ms	4736 KB	Output isn't correct
5	Incorrect	6 ms	4736 KB	Output isn't correct
6	Correct	6 ms	4736 KB	Output is correct
7	Runtime error	339 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
8	Correct	54 ms	4864 KB	Output is correct
9	Incorrect	6 ms	4736 KB	Output isn't correct
10	Incorrect	7 ms	4864 KB	Output isn't correct
11	Incorrect	6 ms	4736 KB	Output isn't correct
12	Incorrect	7 ms	4992 KB	Output isn't correct
13	Incorrect	12 ms	5376 KB	Output isn't correct
14	Correct	904 ms	10060 KB	Output is correct
15	Incorrect	6 ms	4864 KB	Output isn't correct
16	Incorrect	6 ms	4864 KB	Output isn't correct
17	Incorrect	6 ms	4864 KB	Output isn't correct
18	Incorrect	6 ms	4864 KB	Output isn't correct
19	Incorrect	6 ms	4864 KB	Output isn't correct
20	Incorrect	5 ms	4864 KB	Output isn't correct
21	Incorrect	6 ms	4864 KB	Output isn't correct
22	Incorrect	6 ms	4864 KB	Output isn't correct
23	Incorrect	6 ms	4992 KB	Output isn't correct
24	Incorrect	6 ms	4992 KB	Output isn't correct
25	Incorrect	6 ms	4992 KB	Output isn't correct
26	Incorrect	6 ms	4992 KB	Output isn't correct
27	Incorrect	6 ms	5120 KB	Output isn't correct
28	Incorrect	6 ms	5120 KB	Output isn't correct
29	Incorrect	6 ms	5120 KB	Output isn't correct
30	Incorrect	6 ms	4992 KB	Output isn't correct
31	Incorrect	8 ms	5120 KB	Output isn't correct
32	Incorrect	7 ms	5120 KB	Output isn't correct
33	Incorrect	16 ms	6400 KB	Output isn't correct
34	Incorrect	17 ms	6528 KB	Output isn't correct
35	Runtime error	266 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
36	Incorrect	20 ms	6656 KB	Output isn't correct
37	Incorrect	22 ms	6656 KB	Output isn't correct
38	Runtime error	273 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
39	Incorrect	14 ms	7040 KB	Output isn't correct
40	Incorrect	22 ms	6908 KB	Output isn't correct
41	Runtime error	301 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
42	Incorrect	25 ms	7168 KB	Output isn't correct
43	Incorrect	27 ms	7288 KB	Output isn't correct
44	Runtime error	293 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
45	Incorrect	30 ms	7416 KB	Output isn't correct
46	Incorrect	34 ms	7416 KB	Output isn't correct
47	Runtime error	289 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
48	Incorrect	35 ms	7800 KB	Output isn't correct
49	Incorrect	37 ms	7672 KB	Output isn't correct
50	Runtime error	300 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
51	Incorrect	54 ms	7928 KB	Output isn't correct
52	Incorrect	51 ms	8056 KB	Output isn't correct
53	Runtime error	295 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
54	Incorrect	40 ms	8184 KB	Output isn't correct
55	Incorrect	52 ms	8312 KB	Output isn't correct
56	Runtime error	291 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
57	Incorrect	45 ms	8440 KB	Output isn't correct
58	Incorrect	59 ms	8440 KB	Output isn't correct
59	Runtime error	273 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
60	Incorrect	70 ms	8696 KB	Output isn't correct
61	Incorrect	70 ms	8824 KB	Output isn't correct
62	Runtime error	289 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
63	Execution timed out	1073 ms	8696 KB	Time limit exceeded
64	Incorrect	85 ms	8696 KB	Output isn't correct
65	Incorrect	77 ms	8824 KB	Output isn't correct
66	Incorrect	79 ms	8696 KB	Output isn't correct
67	Execution timed out	1077 ms	8696 KB	Time limit exceeded
68	Incorrect	65 ms	8696 KB	Output isn't correct
69	Incorrect	66 ms	8696 KB	Output isn't correct
70	Incorrect	65 ms	8696 KB	Output isn't correct
71	Incorrect	63 ms	8696 KB	Output isn't correct
72	Incorrect	68 ms	8696 KB	Output isn't correct
73	Runtime error	468 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
74	Runtime error	494 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
75	Runtime error	497 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
76	Runtime error	507 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
77	Runtime error	504 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
78	Runtime error	447 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
79	Runtime error	458 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
80	Runtime error	451 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
81	Runtime error	497 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
82	Runtime error	449 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
83	Runtime error	432 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
84	Runtime error	453 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
85	Runtime error	419 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
86	Runtime error	380 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
87	Runtime error	369 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
88	Runtime error	355 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
89	Runtime error	359 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
90	Runtime error	359 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
91	Runtime error	356 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
92	Runtime error	353 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)