Submission #239759

#	Time	Username	Problem	Language	Result	Execution time	Memory
239759		ne4eHbKa	Clickbait (COCI18_clickbait)	C++17	120 / 120	13 ms	3072 KiB

clickbait

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

template<typename t> void umax(t &a, t b) {a = max(a, b);}
template<typename t> void umin(t &a, t b) {a = min(a, b);}

auto steps = initializer_list< pair<int, int> > {
    {+1, +0},
    {+0, +1},
    {-1, -0},
    {-0, -1}
};
#define ft first
#define sd second

const int N = 1024;

struct cont;

cont* follow_pipe(int, int);
void extend(cont*, int, int);

int n, m;
string a[N];

bool valid(int i, int j) {
    return i >= 0 && j >= 0 && i < n && j < m;
}

bool dig(int i, int j) {
    if(!valid(i, j)) return false;
    return a[i][j] >= '0' && a[i][j] <= '9';
}

bool pipe(int i, int j) {
    if(!valid(i, j)) return false;
    int c = a[i][j];
    return c == '|' || c == '-' || c == '+';
}

struct cont {
    int lx{n}, ly{m}, rx{-1}, ry{-1};
    map<int, cont*> nx;
    string name; int nmx, nmy{m};
    cont(int i, int j) {
        extend(this, i, j);
        for(name = ""; nmy < m && dig(nmx, nmy); ++nmy)
            name += a[nmx][nmy];
        for(int i = rx; i >= lx; --i) {
            cont*
            c = follow_pipe(i, ly - 2); if(c) nx[-i] = c;
            c = follow_pipe(i, ry + 2); if(c) nx[-i] = c;
        }
    }
    void make() {
        for(auto i : nx) i.sd->make();
        cout << name << '\n';
    }
};

bool mk[N][N];

void extend(cont *c, int i, int j) {
    if(!valid(i, j) || pipe(i, j) || mk[i][j]) return;
    mk[i][j] = true;
    umin(c->lx, i);
    umax(c->rx, i);
    umin(c->ly, j);
    umax(c->ry, j);
    if(dig(i, j)) {
        umin(c->nmy, j);
        c->nmx = i;
    }
    for(auto s : steps)
        extend(c, i + s.ft, j + s.sd);
}

cont* follow_pipe(int i, int j) {
    if(!pipe(i, j) || mk[i][j]) return 0;
    mk[i][j] = true;
    for(auto s : steps) {
        int x = i + s.ft;
        int y = j + s.sd;
        if(!pipe(x, y)) continue;
        if(a[x][y] != a[i][j] &&
           a[x][y] != '+' &&
           a[i][j] != '+') continue;
        cont* res = follow_pipe(x, y);
        if(res) return res;
    }
    if(i + 2 < n
       && a[i][j] == '|'
       && a[i + 1][j] == '-') return new cont(i + 2, j);
    return 0;
}

void solve() {
#ifdef _LOCAL
    memset(mk, 0, sizeof mk);
#endif
    cin >> n >> m;
    for(int i = 0; i < n; ++i) cin >> a[i];
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            if(a[i][j] != '1' || dig(i, j - 1) || dig(i, j + 1)) continue;
            (new cont(i, j))->make();
            return;
        }
    }
    cout << "wat\n";
}

signed main() {
#ifdef _LOCAL
    freopen("in.txt", "r", stdin);
    int t; cin >> t;
    for(int i = 1; i <= t; ++i) {
        cerr << "case #" << i << endl;
        solve();
        cerr << endl;
    }
#else
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
#endif
}

• Subtask 1: 120 / 120