Submission #219456

#	Time	Username	Problem	Language	Result	Execution time	Memory
219456		Vimmer	Skandi (COCI20_skandi)	C++14	18 / 110	24 ms	1792 KiB

Main

#include <bits/stdc++.h>

//#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 75005
#define M ll(1e9 + 7)


using namespace std;

typedef long double ld;
typedef long long ll;
typedef short int si;





int idr[501][501];

pair <int, int> conv[25005];

int a[25005][2];

vector <int> gr[25005];

vector <pair <int, pair <int, int> > > pr;

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

    int n, m;

    cin >> n >> m;

    string s[n];

    int id = 0;

    for (int i = 0; i < n; i++) {cin >> s[i]; for (int j = 0; j < m; j++) {idr[i][j] = id++; conv[idr[i][j]] = {i, j};} }

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
        {
            id = idr[i][j];

            int y = j + 1;

            if (s[i][j] != '1') continue;

            while (y < m && s[i][y] == '0') {gr[idr[i][y]].pb(sz(pr)); y++;}

            a[id][0] = y - j - 1;

            y = i + 1;

            while (y < n && s[y][j] == '0') {gr[idr[y][j]].pb(sz(pr) + 1); y++;}

            a[id][1] = y - i - 1;

            pr.pb({a[id][0], {0, id}});

            pr.pb({a[id][1], {1, id}});
        }

    bool mk[n][m];

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) mk[i][j] = s[i][j] - '0';

    vector <pair <int, pair <int, int> > > g; g.clear();

    while (1)
    {
        int mx = 0, tp, id, mt = 1e9, mkr = 1e9;

        for (auto it : pr)
        {
            if (it.F == 0) continue;

            int kl = 0, lst = it.F;

            set <int> se; se.clear();

            if (it.S.F == 0)
            {
                int y = conv[it.S.S].S + 1, x = conv[it.S.S].F;

                while (y < m && s[x][y] == '0')
                {
                    if (!mk[x][y]) for (auto itr : gr[idr[x][y]]) {pr[itr].F--; if (pr[itr].F == 0) kl++; se.insert(itr); }

                    y++;
                }
            }
            else
            {
                int y = conv[it.S.S].S, x = conv[it.S.S].F + 1;

                while (x < n && s[x][y] == '0')
                {
                    if (!mk[x][y]) for (auto itr : gr[idr[x][y]]) {pr[itr].F--; if (pr[itr].F == 0) kl++; se.insert(itr);}

                    x++;
                }
            }

            if (mx < kl)
            {
                mx = kl;

                tp = it.S.F;

                id = it.S.S;

                mt = lst;

                mkr = sz(se);
            }

            if (mx == kl && mt < lst)
            {
                mx = kl;

                tp = it.S.F;

                id = it.S.S;

                mt = lst;

                mkr = sz(se);
            }

            if (mx == kl && mt == lst && mkr < sz(se))
            {
                mx = kl;

                tp = it.S.F;

                id = it.S.S;

                mt = lst;

                mkr = sz(se);
            }
            if (it.S.F == 0)
            {
                int y = conv[it.S.S].S + 1, x = conv[it.S.S].F;

                while (y < m && s[x][y] == '0')
                {
                    if (!mk[x][y]) for (auto itr : gr[idr[x][y]]) pr[itr].F++;

                    y++;
                }
            }
            else
            {
                int y = conv[it.S.S].S, x = conv[it.S.S].F + 1;

                while (x < n && s[x][y] == '0')
                {
                    if (!mk[x][y]) for (auto itr : gr[idr[x][y]]) pr[itr].F++;

                    x++;
                }
            }
        }

        if (mx == 0) break;

        g.pb({tp, {conv[id].F, conv[id].S}});

        if (tp == 0)
            {
                int y = conv[id].S + 1, x = conv[id].F;

                while (y < m && s[x][y] == '0')
                {
                    if (!mk[x][y]) for (auto itr : gr[idr[x][y]]) pr[itr].F--;

                    mk[x][y] = 1;

                    y++;
                }
            }
            else
            {
                int y = conv[id].S, x = conv[id].F + 1;

                while (x < n && s[x][y] == '0')
                {
                    if (!mk[x][y]) for (auto itr : gr[idr[x][y]]) pr[itr].F--;

                    mk[x][y] = 1;

                    x++;
                }
            }
    }

    cout << sz(g) << endl;

    for (auto it : g) cout << it.S.F + 1 << " " << it.S.S + 1 << " " << (it.F == 0 ? "DESNO" : "DOLJE") << endl;
}

• Subtask 1: 18 / 18
• Subtask 2: 0 / 32
• Subtask 3: 0 / 60