제출 #239731

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
239731		Vimmer	Clickbait (COCI18_clickbait)	C++14	60 / 120	17 ms	10624 KiB

clickbait

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")

#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 101001
#define M ll(1e9 + 7)
#define inf 1e9 + 1e9


using namespace std;
//using namespace __gnu_pbds;

typedef long double ld;
typedef long long ll;
typedef short int si;
typedef array <int, 4> a4;

//typedef tree <int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;



vector <pair <int, int> > g[40];

int a[1005][1005];

a4 pos[40];

string s[1005];

int b[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}, n, m;

vector <int> ans;

void dfs(int v)
{
    for (auto it : g[v]) dfs(it.S);

    ans.pb(v);
}
void rec(int x, int y, int nm, int px, int py, int h)
{
    for (int i = 0; i < 4; i++)
    {
        int cx = x + b[i][0];

        int cy = y + b[i][1];

        if (cx == px && cy == py) continue;

        if (cx < 0 || cx > n || cy < 0 || cy > m || s[cx][cy] == '.') continue;

        if (s[cx][cy] != s[x][y] && s[x][y] != '+' && s[cx][cy] != '+') g[nm].pb({h, a[cx][cy]});
            else
            {
                px = x; py = y;

                x = cx; y = cy;

                i = -1;

                continue;
            }

        return;
    }
}

int main()
{
    //freopen("input.txt", "r", stdin); //freopen("output4.txt", "w", stdout);

    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m;

    for (int i = 0; i < n; i++) cin >> s[i];

    int mx = 0;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
        {
            if (s[i][j] == '.' || s[i][j] == '-' || s[i][j] == '|' || s[i][j] == '+' || a[i][j] != 0) continue;

            int nm = 0; mx = max(mx, nm);

            int pj = j;

            while (!(s[i][pj] == '.' || s[i][pj] == '-' || s[i][pj] == '|' || s[i][pj] == '+')) pj++;

            pj--;

            while (pj >= j) {nm *= 10; nm += s[i][pj] - '0'; pj--;}

            mx = max(mx, nm);

            int xl = i, xr = i, yl = j, yr = j;

            while (s[xr][j] != '-') xr++;

            while (s[xl][j] != '-') xl--;

            while (s[i][yr] != '|') yr++;

            while (s[i][yl] != '|') yl--;

            for (int x = xl; x <= xr; x++)
                for (int y = yl; y <= yr; y++) a[x][y] = nm;

            pos[nm] = {xl, yl, xr, yr};
        }

    for (int nm = 1; nm <= mx; nm++)
    {
        int xl = pos[nm][0], yl = pos[nm][1], xr = pos[nm][2], yr = pos[nm][3];

        if (yl - 1 != 0)
            for (int x = xl; x <= xr; x++)
              if (s[x][yl - 1] == '-')
                rec(x, yl - 1, nm, x, yl, x);

        if (yr + 1 != m)
            for (int x = xl; x <= xr; x++)
              if (s[x][yr + 1] == '-')
                rec(x, yr + 1, nm, x, yr, x);
    }

    for (int i = 1; i <= mx; i++) {sort(g[i].begin(), g[i].end()); reverse(g[i].begin(), g[i].end());}

    dfs(1);

    for (auto it : ans) cout << it << endl;
}

• Subtask 1: 60 / 120