Submission #1102839

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1102839	2024-10-19T04:46:15 Z	salmon	Mecho (IOI09_mecho)	C++14	0 / 100	43 ms	8288 KB

mecho

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

int N;
int S;
vector<pair<int,int>> trans = {{1,0}, {-1,0},{0,1},{0,-1}};
char clst[810][810];
int s1,s2;
int f1,f2;
queue<pair<int,int>> q[2];
queue<pair<int,int>> m[2];
bool visited[810][810];
bool vt[810][810];
int cq,cm;

bool check(int i, int j){
    if(i < 0) return false;
    if(i >= N) return false;
    if(j < 0) return false;
    if(j >= N) return false;
    return true;
}

void spreadhoney(int it){
    while(!q[it].empty()){
        pair<int,int> ii = q[it].front();
        q[it].pop();

        int i = ii.first;
        int j = ii.second;

        visited[i][j] = true;
        vt[i][j] = true;

        for(pair<int,int> ii : trans){
            int ni = ii.first + i;
            int nj = ii.second + j;

            if(!check(ni,nj)) continue;
            if(visited[ni][nj]) continue;
            q[1 - it].push({ni,nj});
        }
    }
}

int main(){
    scanf(" %d",&N);
    scanf(" %d",&S);

    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            scanf(" %c",&clst[i][j]);
        }
    }

    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            visited[i][j] = false;
            vt[i][j] = false;
        }
    }

    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(clst[i][j] == 'T'){
                visited[i][j] = true;
                vt[i][j] = true;
            }
            else if(clst[i][j] == 'H'){
                q[1].push({i,j});
            }
            else if(clst[i][j] == 'M'){
                s1 = i;
                s2 = j;
            }
            else if(clst[i][j] == 'D'){
                f1 = i;
                f2 = j;
                visited[i][j] = true;
            }
        }
    }

    cq = 0;
    cm = 0;

    spreadhoney(1);

    vt[s1][s2] = true;

    for(pair<int,int> ii : trans){
        int ni = s1 + ii.first;
        int nj = s2 + ii.second;

        if(!check(ni,nj)) continue;
        m[0].push({ni,nj});
    }

    bool flag;

    for(int i = 0; i < N * N; i++){
        q[0].push({i,i});
    }
    return 0;

    while(true){
        int it = cm % 2;

        bool done = false;

        for(int i = 0; i < S; i++, cm++){
            it = cm % 2;

            while(!m[it].empty()){
                pair<int,int> ii = m[it].front();
                m[it].pop();

                int i = ii.first;
                int j = ii.second;

                if(i == f1 && j == f2){
                    done = true;
                    flag = true;
                    break;
                }
                if(vt[i][j]) continue;
                vt[i][j] = true;

                for(pair<int,int> ii : trans){
                    int ni = i + ii.first;
                    int nj = j + ii.second;

                    if(!check(ni,nj)) continue;
                    if(vt[ni][nj]) continue;
                    m[1 - it].push({ni,nj});
                }
            }

            if(done) break;

            if(m[1 - it].empty()){
                done = true;
                flag = false;
                break;
            }
        }

        if(done) break;

        it = cq % 2;
        spreadhoney(it);
        cq++;
    }

    if(!flag || true){
        printf("-1");
        return 0;
    }

    int s = 0;
    int e = 800*800;
    int m1;

    while(s != e){
        m1 = (s + e + 1)/2;

        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                visited[i][j] = false;
                vt[i][j] = false;
            }
        }

        while(!m[0].empty()) m[0].pop();
        while(!m[1].empty()) m[1].pop();
        while(!q[0].empty()) q[0].pop();
        while(!q[1].empty()) q[1].pop();

        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(clst[i][j] == 'T'){
                    visited[i][j] = true;
                    vt[i][j] = true;
                }
                else if(clst[i][j] == 'H'){
                    q[1].push({i,j});
                }
                else if(clst[i][j] == 'D'){
                    visited[i][j] = true;
                }
            }
        }

        cq = 0;
        cm = 0;

        spreadhoney(1);

        vt[s1][s2] = true;

        for(pair<int,int> ii : trans){
            int ni = s1 + ii.first;
            int nj = s2 + ii.second;

            if(!check(ni,nj)) continue;
            m[0].push({ni,nj});
        }

        for(int i = 0; i < m1; i++, cq++){
            int it = cq % 2;

            spreadhoney(it);
        }

        if(visited[s1][s2]){
            e = m1 - 1;
            continue;
        }

        /*for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                printf("%d ",visited[i][j]);
            }
            printf("\n");
        }
        printf("\n");*/

        bool flag;

        while(true){
            int it = cm % 2;

            bool done = false;

            for(int i = 0; i < S; i++, cm++){
                it = cm % 2;

                while(!m[it].empty()){
                    pair<int,int> ii = m[it].front();
                    m[it].pop();

                    int i = ii.first;
                    int j = ii.second;
                    //printf("%d %d\n",i,j);

                    if(i == f1 && j == f2){
                        done = true;
                        flag = true;
                        break;
                    }
                    if(vt[i][j]) continue;
                    vt[i][j] = true;

                    for(pair<int,int> ii : trans){
                        int ni = i + ii.first;
                        int nj = j + ii.second;

                        if(!check(ni,nj)) continue;
                        m[1 - it].push({ni,nj});
                    }
                }
                //printf("\n");

                if(done) break;

                if(m[1 - it].empty()){
                    done = true;
                    flag = false;
                    break;
                }
            }

            if(done) break;

            it = cq % 2;
            spreadhoney(it);
            cq++;
        }

        if(flag){
            s = m1;
        }
        else{
            e = m1 - 1;
        }
    }

    printf("%d",s);
}
/*
7 3
TTTTTTT
TGGGGGT
TGGGGGG
MGGGGGD
TGGTTTT
TGGGGGT
TTTTTHT
*/

Compilation message

mecho.cpp: In function 'int main()':
mecho.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
mecho.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     scanf(" %d",&S);
      |     ~~~~~^~~~~~~~~~
mecho.cpp:52:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |             scanf(" %c",&clst[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1

0.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	336 KB	Output isn't correct
2	Incorrect	1 ms	456 KB	Output isn't correct
3	Incorrect	1 ms	336 KB	Output isn't correct
4	Incorrect	1 ms	336 KB	Output isn't correct
5	Incorrect	1 ms	336 KB	Output isn't correct
6	Incorrect	1 ms	336 KB	Output isn't correct
7	Incorrect	28 ms	8016 KB	Output isn't correct
8	Incorrect	1 ms	336 KB	Output isn't correct
9	Incorrect	1 ms	504 KB	Output isn't correct
10	Incorrect	1 ms	336 KB	Output isn't correct
11	Incorrect	1 ms	500 KB	Output isn't correct
12	Incorrect	1 ms	592 KB	Output isn't correct
13	Incorrect	1 ms	592 KB	Output isn't correct
14	Incorrect	1 ms	592 KB	Output isn't correct
15	Incorrect	0 ms	336 KB	Output isn't correct
16	Incorrect	1 ms	504 KB	Output isn't correct
17	Incorrect	1 ms	336 KB	Output isn't correct
18	Incorrect	1 ms	336 KB	Output isn't correct
19	Incorrect	1 ms	336 KB	Output isn't correct
20	Incorrect	1 ms	336 KB	Output isn't correct
21	Incorrect	1 ms	336 KB	Output isn't correct
22	Incorrect	1 ms	460 KB	Output isn't correct
23	Incorrect	1 ms	592 KB	Output isn't correct
24	Incorrect	1 ms	504 KB	Output isn't correct
25	Incorrect	1 ms	592 KB	Output isn't correct
26	Incorrect	1 ms	592 KB	Output isn't correct
27	Incorrect	1 ms	592 KB	Output isn't correct
28	Incorrect	1 ms	592 KB	Output isn't correct
29	Incorrect	1 ms	592 KB	Output isn't correct
30	Incorrect	1 ms	592 KB	Output isn't correct
31	Incorrect	1 ms	592 KB	Output isn't correct
32	Incorrect	1 ms	592 KB	Output isn't correct
33	Incorrect	6 ms	2128 KB	Output isn't correct
34	Incorrect	8 ms	2388 KB	Output isn't correct
35	Incorrect	8 ms	2384 KB	Output isn't correct
36	Incorrect	8 ms	2692 KB	Output isn't correct
37	Incorrect	8 ms	2640 KB	Output isn't correct
38	Incorrect	9 ms	2640 KB	Output isn't correct
39	Incorrect	10 ms	3152 KB	Output isn't correct
40	Incorrect	9 ms	2968 KB	Output isn't correct
41	Incorrect	10 ms	3152 KB	Output isn't correct
42	Incorrect	14 ms	3672 KB	Output isn't correct
43	Incorrect	13 ms	3676 KB	Output isn't correct
44	Incorrect	14 ms	4184 KB	Output isn't correct
45	Incorrect	15 ms	4188 KB	Output isn't correct
46	Incorrect	16 ms	4364 KB	Output isn't correct
47	Incorrect	15 ms	4432 KB	Output isn't correct
48	Incorrect	19 ms	4688 KB	Output isn't correct
49	Incorrect	19 ms	5076 KB	Output isn't correct
50	Incorrect	21 ms	5188 KB	Output isn't correct
51	Incorrect	21 ms	5456 KB	Output isn't correct
52	Incorrect	29 ms	5212 KB	Output isn't correct
53	Incorrect	20 ms	5848 KB	Output isn't correct
54	Incorrect	25 ms	5900 KB	Output isn't correct
55	Incorrect	24 ms	6472 KB	Output isn't correct
56	Incorrect	25 ms	6480 KB	Output isn't correct
57	Incorrect	28 ms	6728 KB	Output isn't correct
58	Incorrect	27 ms	7248 KB	Output isn't correct
59	Incorrect	28 ms	7240 KB	Output isn't correct
60	Incorrect	30 ms	7672 KB	Output isn't correct
61	Incorrect	34 ms	8016 KB	Output isn't correct
62	Incorrect	30 ms	8016 KB	Output isn't correct
63	Incorrect	30 ms	7484 KB	Output isn't correct
64	Incorrect	32 ms	7504 KB	Output isn't correct
65	Incorrect	32 ms	7504 KB	Output isn't correct
66	Incorrect	30 ms	7496 KB	Output isn't correct
67	Incorrect	33 ms	7500 KB	Output isn't correct
68	Incorrect	33 ms	8016 KB	Output isn't correct
69	Incorrect	32 ms	7968 KB	Output isn't correct
70	Incorrect	43 ms	7496 KB	Output isn't correct
71	Incorrect	32 ms	7904 KB	Output isn't correct
72	Incorrect	31 ms	7444 KB	Output isn't correct
73	Incorrect	30 ms	8288 KB	Output isn't correct
74	Incorrect	30 ms	8272 KB	Output isn't correct
75	Incorrect	30 ms	8164 KB	Output isn't correct
76	Incorrect	28 ms	8264 KB	Output isn't correct
77	Incorrect	30 ms	8164 KB	Output isn't correct
78	Incorrect	30 ms	8264 KB	Output isn't correct
79	Incorrect	30 ms	8264 KB	Output isn't correct
80	Incorrect	31 ms	8264 KB	Output isn't correct
81	Incorrect	32 ms	8268 KB	Output isn't correct
82	Incorrect	30 ms	8272 KB	Output isn't correct
83	Incorrect	32 ms	8264 KB	Output isn't correct
84	Incorrect	31 ms	8272 KB	Output isn't correct
85	Incorrect	31 ms	8264 KB	Output isn't correct
86	Incorrect	31 ms	8092 KB	Output isn't correct
87	Incorrect	31 ms	8264 KB	Output isn't correct
88	Incorrect	41 ms	8124 KB	Output isn't correct
89	Incorrect	31 ms	8092 KB	Output isn't correct
90	Incorrect	29 ms	8008 KB	Output isn't correct
91	Incorrect	36 ms	8064 KB	Output isn't correct
92	Incorrect	31 ms	8008 KB	Output isn't correct