Submission #239790

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
239790	2020-06-17T09:56:11 Z	VEGAnn	Clickbait (COCI18_clickbait)	C++14	12 / 120	56 ms	61816 KB

clickbait

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define PB push_back
#define sz(x) ((int)x.size())
#define i3 array<int,3>
#define i2 array<int,2>
#define all(x) x.begin(),x.end()
using namespace std;
using namespace __gnu_pbds;
typedef long double ld;
typedef long long ll;
const int N = 1010;
const int M = 510;
const int K = 110;
const int T = 2010;
const int oo = 2e9;
const int MX = 1000100;
vector<int> ts;
string mem[MX], nw;
vector<i2> g[MX], vc;
char c[N][N];
int n, m, cnt = 0, mrk[N][N];
bool used[N][N], ok[N][N];

void filll(int x, int y, int cl){
    if (mrk[x][y] > 0) return;

    mrk[x][y] = cl;

    if (c[x][y] == '-' || c[x][y] == '|') return;

    if (x > 0) filll(x - 1, y, cl);
    if (x < n - 1) filll(x + 1, y, cl);
    if (y < m - 1) filll(x, y + 1, cl);
    if (y > 0) filll(x, y - 1, cl);
}

void dfs(int v){
    if (sz(g[v]) > 0){
        sort(all(g[v]));
        reverse(all(g[v]));

        for (i2 u : g[v])
            dfs(u[1]);
    }

    ts.PB(v);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> m;

    for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) {
        cin >> c[i][j];
        ok[i][j] = bool(c[i][j] == '|' || c[i][j] == '+' || c[i][j] == '-');
    }

    for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
        if (c[i][j] >= '1' && c[i][j] <= '9' && mrk[i][j] == 0){
            nw = c[i][j];

            int jj = j + 1;

            while (jj < m && c[i][jj] >= '0' && c[i][jj] <= '9'){
                nw += c[i][jj];
                jj++;
            }

            mem[++cnt] = nw;

            filll(i, j, cnt);

            if (mem[cnt] == "1") continue;

            vc.PB({i, j});
        }


    for (i2 CUR : vc) {
        int i = CUR[0], j = CUR[1];

        int ii = i, mj = -1;

        int jj = j;

        while (c[ii][jj] != '-')
            ii--;

        while (c[ii][jj] != '+'){
            if (c[ii - 1][jj] == '|')
                mj = jj;

            jj--;
        }

        jj = j;

        while (c[ii][jj] != '+'){
            if (c[ii - 1][jj] == '|')
                mj = jj;

            jj++;
        }

        jj = mj;

        used[ii][jj] = 1;

        ii--;

        while (1){
            used[ii][jj] = 1;

            if (c[ii][jj] == '|')
                ii--;
            else if (c[ii][jj] == '+'){
                if (jj > 0 && !used[ii][jj - 1] && ok[ii][jj - 1])
                    jj--;
                else if (jj + 1 < m && !used[ii][jj + 1] && ok[ii][jj + 1])
                    jj++;
                else ii--;
            } else {
                if (jj > 0 && !used[ii][jj - 1] && ok[ii][jj - 1])
                    jj--;
                else jj++;

                if (mrk[ii][jj] > 0){
                    g[mrk[ii][jj]].PB({ii, cnt});
                    break;
                }
            }
        }
    }

    dfs(1);

    for (int cr : ts)
        cout << mem[cr] << '\n';

    return 0;
}

Subtask #1

12.0 / 120.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	39 ms	55672 KB	Output isn't correct
2	Incorrect	34 ms	55424 KB	Output isn't correct
3	Incorrect	34 ms	55544 KB	Output isn't correct
4	Correct	34 ms	55288 KB	Output is correct
5	Incorrect	35 ms	55544 KB	Output isn't correct
6	Incorrect	34 ms	55544 KB	Output isn't correct
7	Incorrect	35 ms	55552 KB	Output isn't correct
8	Incorrect	37 ms	56448 KB	Output isn't correct
9	Incorrect	36 ms	60032 KB	Output isn't correct
10	Incorrect	56 ms	61816 KB	Output isn't correct