제출 #219428

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
219428		Vimmer	Skandi (COCI20_skandi)	C++14	0 / 110	7 ms	1920 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 <pair <int, int> > gr[25005];

set <pair <int, pair <int, int> > > se;

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({0, id}); y++;}

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

            y = i + 1;

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

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

            se.insert({a[id][0], {id, 0}});

            se.insert({a[id][1], {id, 1}});
        }

    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 (sz(se) > 0 && (*se.rbegin()).F > 0)
    {
        pair <int, pair <int, int> > pt = *se.rbegin(); se.erase(*se.rbegin());

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

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

            while (y < m && s[x][y] == '0')
                {
                    if (!mk[x][y])

                    for (auto it : gr[idr[x][y]])
                    {
                        if (se.find({a[it.S][it.F], {it.S, it.F}}) != se.end())
                            {
                                se.erase({a[it.S][it.F], {it.S, it.F}});

                                a[it.S][it.F]--;

                                se.insert({a[it.S][it.F], {it.S, it.F}});
                            }
                    }

                    mk[x][y] = 1;

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

            while (x < n && s[x][y] == '0')
                {
                    if (!mk[x][y])

                    for (auto it : gr[idr[x][y]])
                    {
                        if (se.find({a[it.S][it.F], {it.S, it.F}}) != se.end())
                            {
                                se.erase({a[it.S][it.F], {it.S, it.F}});

                                a[it.S][it.F]--;

                                se.insert({a[it.S][it.F], {it.S, it.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: 0 / 18
• Subtask 2: 0 / 32
• Subtask 3: 0 / 60