oj.uz

Submission #219447

# Submission time Handle Problem Language Result Execution time Memory
219447 2020-04-05T10:35:13 Z Vimmer Skandi (COCI20_skandi) C++14
0 / 110
 6 ms 1920 KB 
#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], {0, id}});

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

        swap(pt.S.F, pt.S.S);

        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.F, it.S}}) != se.end())
                            {
                                se.erase({a[it.S][it.F], {it.F, it.S}});

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

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

                    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.F, it.S}}) != se.end())
                            {
                                se.erase({a[it.S][it.F], {it.F, it.S}});

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

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

                    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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 896 KB Correct.
2 Correct 5 ms 896 KB Correct.
3 Incorrect 5 ms 896 KB First line is not correct.
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1920 KB Correct.
2 Correct 6 ms 1408 KB Correct.
3 Correct 6 ms 1792 KB Correct.
4 Correct 6 ms 1408 KB Correct.
5 Incorrect 6 ms 1408 KB First line is not correct.
6 Halted 0 ms 0 KB -

Subtask #3
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 896 KB Correct.
2 Correct 5 ms 896 KB Correct.
3 Incorrect 5 ms 896 KB First line is not correct.
4 Halted 0 ms 0 KB -