oj.uz

Submission #219454

# Submission time Handle Problem Language Result Execution time Memory
219454 2020-04-05T10:57:32 Z Vimmer Skandi (COCI20_skandi) C++14
18 / 110
 11 ms 1792 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 <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;

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

            int kl = 0, lst = it.F;

            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++;}

                    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++;}

                    x++;
                }
            }

            if (mx < kl)
            {
                mx = kl;

                tp = it.S.F;

                id = it.S.S;

                mt = lst;
            }

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

                tp = it.S.F;

                id = it.S.S;

                mt = lst;
            }
            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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 896 KB Correct.
2 Correct 5 ms 896 KB Correct.
3 Correct 5 ms 1024 KB Correct.
4 Correct 5 ms 1024 KB Correct.
5 Correct 5 ms 896 KB Correct.
6 Correct 5 ms 896 KB Correct.
7 Correct 5 ms 896 KB Correct.
8 Correct 5 ms 1024 KB Correct.
9 Correct 5 ms 896 KB Correct.
10 Correct 5 ms 896 KB Correct.
11 Correct 6 ms 1016 KB Correct.
12 Correct 5 ms 896 KB Correct.
13 Correct 5 ms 896 KB Correct.
14 Correct 5 ms 896 KB Correct.
15 Correct 5 ms 896 KB Correct.
16 Correct 5 ms 896 KB Correct.
17 Correct 5 ms 896 KB Correct.
18 Correct 5 ms 1024 KB Correct.
19 Correct 5 ms 896 KB Correct.
20 Correct 5 ms 896 KB Correct.
21 Correct 5 ms 896 KB Correct.
22 Correct 5 ms 896 KB Correct.
23 Correct 5 ms 1024 KB Correct.

Subtask #2
0.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1792 KB Correct.
2 Correct 6 ms 1408 KB Correct.
3 Correct 11 ms 1664 KB Correct.
4 Correct 6 ms 1280 KB Correct.
5 Incorrect 8 ms 1280 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 Correct 5 ms 1024 KB Correct.
4 Correct 5 ms 1024 KB Correct.
5 Correct 5 ms 896 KB Correct.
6 Correct 5 ms 896 KB Correct.
7 Correct 5 ms 896 KB Correct.
8 Correct 5 ms 1024 KB Correct.
9 Correct 5 ms 896 KB Correct.
10 Correct 5 ms 896 KB Correct.
11 Correct 6 ms 1016 KB Correct.
12 Correct 5 ms 896 KB Correct.
13 Correct 5 ms 896 KB Correct.
14 Correct 5 ms 896 KB Correct.
15 Correct 5 ms 896 KB Correct.
16 Correct 5 ms 896 KB Correct.
17 Correct 5 ms 896 KB Correct.
18 Correct 5 ms 1024 KB Correct.
19 Correct 5 ms 896 KB Correct.
20 Correct 5 ms 896 KB Correct.
21 Correct 5 ms 896 KB Correct.
22 Correct 5 ms 896 KB Correct.
23 Correct 5 ms 1024 KB Correct.
24 Correct 6 ms 1792 KB Correct.
25 Correct 6 ms 1408 KB Correct.
26 Correct 11 ms 1664 KB Correct.
27 Correct 6 ms 1280 KB Correct.
28 Incorrect 8 ms 1280 KB First line is not correct.
29 Halted 0 ms 0 KB -