답안 #810466

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
810466	2023-08-06T09:59:44 Z	asdasdqwer	Mecho (IOI09_mecho)	C++17	0 / 100	378 ms	16952 KB

mecho

#include <bits/stdc++.h>
using namespace std;

#define int int64_t
#define mp make_pair
#define pii pair<int, int>
#define f first
#define s second
#define tii array<int, 3>
#define all(x) x.begin(), x.end()
#define pb push_back
#define ppi pair<pii, int>

vector<pii> dir = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

pii operator+(const pii &x, const pii &y) {
    return mp(x.f+y.f, x.s+y.s);
}

bool check(const pii &x, int n) {
    return x.f >= 0 && x.f < n && x.s >= 0 && x.s < n;
}

// void printArr(vector<vector<int>> &a) {
//     int n = a.size();
//     for (int i=0;i<n;i++) {
//         fmt::print("{}\n", a[i]);
//     }
// }

bool test(int wait, vector<vector<int>> &grid, int st, pii &pos, pii &des) {
    // simulate "wait"
    int n=grid.size();
    vector<vector<int>> status(n, vector<int>(n, 0));
    queue<pair<pii, int>> q;
    vector<pii> hv;
    for (int i=0;i<n;i++) {
        for (int j=0;j<n;j++) {
            if (grid[i][j]==0) {
                hv.pb(mp(i, j));
            }
        }
    }

    for (auto &x:hv) {
        q.push(mp(x, 0));
        status[x.f][x.s]=1;
    }

    while (!q.empty() && q.front().s != wait) {
        ppi t = q.front();q.pop();
        if (t.s != wait) {
            for (int i=0;i<4;i++) {
                pii add = t.f + dir[i];
                if (check(add, n) && status[add.f][add.s] != 1 && grid[add.f][add.s]==1) {
                    status[add.f][add.s]=1;
                    q.push(mp(add, t.s+1));
                }
            }
        }
    }

    queue<ppi> pq;
    pq.push(mp(pos, 0));
    int endB = wait;
    int endP = 0;
    while (true) {
        endB++;endP+=st;
        if (pq.empty()) return false;
        while (!pq.empty() && pq.front().s != endP) {
            ppi t=pq.front();pq.pop();
            if (t.f==des) {
                return true;
            }

            if (status[t.f.f][t.f.s]==1) {
                continue;
            }

            for (int i=0;i<4;i++) {
                pii add=t.f + dir[i];
                if (check(add, n) && (status[add.f][add.s]==0) && grid[add.f][add.s]==1) {
                    status[add.f][add.s]=2;
                    pq.push(mp(add, t.s+1));
                }

                else if (check(add, n) && status[add.f][add.s]==0 && grid[add.f][add.s]==-2) {
                    return true;
                } 
            }
        }

        while (!q.empty() && q.front().s != endB) {
            ppi t = q.front();q.pop();
            if (t.s != endB) {
                for (int i=0;i<4;i++) {
                    pii add = t.f + dir[i];
                    if (check(add, n) && status[add.f][add.s] != 1 && grid[add.f][add.s]==1) {
                        status[add.f][add.s]=1;
                        q.push(mp(add, t.s+1));
                    }
                }
            }
        }
    }
}

int binSearch(vector<vector<int>> a, int st, pii &pos, pii &des) {
    int n = a.size();
    int l = 0, r = (n*n)+1;

    int ans = -1;
    while (l <= r) {
        int m = l + (r-l)/2;
        bool t = test(m, a, st, pos, des);
        cout << m << " " << t << "\n";
        if (t) {
            l = m+1;
            ans = m;
        }

        else {
            r = m-1;
        }
    }

    return ans;
}

signed main() {
    // freopen("in.txt", "r", stdin);
    int n, st;cin>>n>>st;
    vector<vector<int>> a(n, vector<int>(n, 0));
    pii pos, des;
    for (int i=0;i<n;i++) {
        string s;cin>>s;
        for (int j=0;j<n;j++) {
            if (s[j]=='H')a[i][j]=0;
            if (s[j]=='G')a[i][j]=1;
            if (s[j]=='M') {
                a[i][j]=1;
                pos=mp(i, j);
            }

            if (s[j]=='D') {
                a[i][j]=-2;
                des=mp(i, j);
            }

            if (s[j]=='T')a[i][j]=-1;
        }
    }
    // cout << test(0, a, st, pos, des) << "\n";
    cout << binSearch(a, st, pos, des) << "\n";
}

Subtask #1

0.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1 ms	212 KB	Output isn't correct
2	Incorrect	0 ms	212 KB	Output isn't correct
3	Incorrect	0 ms	212 KB	Output isn't correct
4	Incorrect	0 ms	212 KB	Output isn't correct
5	Incorrect	0 ms	212 KB	Output isn't correct
6	Incorrect	0 ms	212 KB	Output isn't correct
7	Incorrect	293 ms	16380 KB	Output isn't correct
8	Incorrect	1 ms	252 KB	Output isn't correct
9	Incorrect	0 ms	212 KB	Output isn't correct
10	Incorrect	1 ms	212 KB	Output isn't correct
11	Incorrect	0 ms	296 KB	Output isn't correct
12	Incorrect	1 ms	340 KB	Output isn't correct
13	Incorrect	1 ms	340 KB	Output isn't correct
14	Incorrect	2 ms	340 KB	Output isn't correct
15	Incorrect	0 ms	212 KB	Output isn't correct
16	Incorrect	1 ms	212 KB	Output isn't correct
17	Incorrect	1 ms	212 KB	Output isn't correct
18	Incorrect	0 ms	212 KB	Output isn't correct
19	Incorrect	1 ms	212 KB	Output isn't correct
20	Incorrect	1 ms	212 KB	Output isn't correct
21	Incorrect	1 ms	340 KB	Output isn't correct
22	Incorrect	1 ms	340 KB	Output isn't correct
23	Incorrect	1 ms	300 KB	Output isn't correct
24	Incorrect	1 ms	300 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	432 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	28 ms	3372 KB	Output isn't correct
34	Incorrect	25 ms	3372 KB	Output isn't correct
35	Incorrect	34 ms	3284 KB	Output isn't correct
36	Incorrect	32 ms	4240 KB	Output isn't correct
37	Incorrect	35 ms	4268 KB	Output isn't correct
38	Incorrect	41 ms	4260 KB	Output isn't correct
39	Incorrect	40 ms	5340 KB	Output isn't correct
40	Incorrect	44 ms	5420 KB	Output isn't correct
41	Incorrect	56 ms	5304 KB	Output isn't correct
42	Incorrect	51 ms	6496 KB	Output isn't correct
43	Incorrect	54 ms	6492 KB	Output isn't correct
44	Incorrect	70 ms	6484 KB	Output isn't correct
45	Incorrect	69 ms	7776 KB	Output isn't correct
46	Incorrect	65 ms	7776 KB	Output isn't correct
47	Incorrect	96 ms	7788 KB	Output isn't correct
48	Incorrect	79 ms	9200 KB	Output isn't correct
49	Incorrect	84 ms	9208 KB	Output isn't correct
50	Incorrect	98 ms	9188 KB	Output isn't correct
51	Incorrect	94 ms	10736 KB	Output isn't correct
52	Incorrect	98 ms	10752 KB	Output isn't correct
53	Incorrect	124 ms	10664 KB	Output isn't correct
54	Incorrect	128 ms	12392 KB	Output isn't correct
55	Incorrect	111 ms	12368 KB	Output isn't correct
56	Incorrect	146 ms	12376 KB	Output isn't correct
57	Incorrect	144 ms	14172 KB	Output isn't correct
58	Incorrect	129 ms	14180 KB	Output isn't correct
59	Incorrect	191 ms	14168 KB	Output isn't correct
60	Incorrect	154 ms	16084 KB	Output isn't correct
61	Incorrect	144 ms	16076 KB	Output isn't correct
62	Incorrect	217 ms	16076 KB	Output isn't correct
63	Incorrect	321 ms	16260 KB	Output isn't correct
64	Incorrect	320 ms	16076 KB	Output isn't correct
65	Incorrect	291 ms	15948 KB	Output isn't correct
66	Incorrect	315 ms	16220 KB	Output isn't correct
67	Incorrect	331 ms	16056 KB	Output isn't correct
68	Incorrect	355 ms	16140 KB	Output isn't correct
69	Incorrect	305 ms	16144 KB	Output isn't correct
70	Incorrect	330 ms	16140 KB	Output isn't correct
71	Incorrect	355 ms	16140 KB	Output isn't correct
72	Incorrect	378 ms	16152 KB	Output isn't correct
73	Incorrect	267 ms	16944 KB	Output isn't correct
74	Incorrect	342 ms	16940 KB	Output isn't correct
75	Incorrect	351 ms	16952 KB	Output isn't correct
76	Incorrect	351 ms	16948 KB	Output isn't correct
77	Incorrect	339 ms	16944 KB	Output isn't correct
78	Incorrect	319 ms	16828 KB	Output isn't correct
79	Incorrect	292 ms	16836 KB	Output isn't correct
80	Incorrect	324 ms	16836 KB	Output isn't correct
81	Incorrect	292 ms	16820 KB	Output isn't correct
82	Incorrect	308 ms	16868 KB	Output isn't correct
83	Incorrect	304 ms	16776 KB	Output isn't correct
84	Incorrect	294 ms	16692 KB	Output isn't correct
85	Incorrect	342 ms	16776 KB	Output isn't correct
86	Incorrect	328 ms	16700 KB	Output isn't correct
87	Incorrect	304 ms	16692 KB	Output isn't correct
88	Incorrect	307 ms	16672 KB	Output isn't correct
89	Incorrect	309 ms	16544 KB	Output isn't correct
90	Incorrect	314 ms	16592 KB	Output isn't correct
91	Incorrect	299 ms	16548 KB	Output isn't correct
92	Incorrect	351 ms	16572 KB	Output isn't correct