oj.uz

Submission #220634

# Submission time Handle Problem Language Result Execution time Memory
220634 2020-04-08T10:18:10 Z Vimmer Skandi (COCI20_skandi) C++14
64 / 110
 4787 ms 10872 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 250005
#define MOD ll(998244353)

using namespace std;

typedef long long ll;

typedef long double ld;



int mt[N], idr[505][505];

vector <int> g[N];

bool mk[N];

bool kuna(int v)
{
    if (mk[v]) return 0;

    mk[v] = 1;

    for (auto it : g[v])
    {
        if (mt[it] == -1 || kuna(mt[it]))
            {
                mt[it] = v;

                return 1;
            }
    }

    return 0;
}
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];

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

    if (n <= 10 && m <= 10)
    {
        vector <pair <int, int> > g; g.clear();

        for (int i = 0; i < n; i++)
          for (int j = 0; j < m; j++)
            if (s[i][j] == '1' && ((i + 1 != n && s[i + 1][j] == '0') || (j + 1 != m && s[i][j + 1] == '0'))) g.pb({i, j});

        int ans = 1e9;

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

        for (int umsk = 0; umsk < (1 << sz(g)); umsk++)
        {
            if (__builtin_popcount(umsk) >= ans) continue;

            vector <int> pr; pr.clear();

            for (int i = 0; i < sz(g); i++) if ((1 << i) & umsk) pr.pb(i);

            for (int msk = 0; msk < (1 << sz(pr)); msk++)
            {
                bool gd = 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';

                for (int i = 0; i < sz(pr); i++)
                    if ((1 << i) & msk)
                    {
                        int x = g[pr[i]].F, y = g[pr[i]].S;

                        if (y + 1 == m || s[x][y + 1] == '1') {gd = 0; break;}

                        int j = y + 1;

                        while (j < m && s[x][j] == '0') {mk[x][j] = 1; j++;}
                    }
                    else
                    {
                        int x = g[pr[i]].F, y = g[pr[i]].S;

                        if (x + 1 == n || s[x + 1][y] == '1') {gd = 0; break;}

                        int j = x + 1;

                        while (j < n && s[j][y] == '0') {mk[j][y] = 1; j++;}
                    }

                for (int i = 0; i < n; i++)
                    for (int j = 0; j < m; j++) if (!mk[i][j]) gd = 0;

                if (gd)
                {
                    ans = sz(pr);

                    gr.clear();

                    for (int i = 0; i < sz(pr); i++) gr.pb({{g[pr[i]].F, g[pr[i]].S}, (1 << i) & msk});

                    break;
                }
            }
        }

        cout << sz(gr) << endl;

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

        exit(0);
    }
    int id = 0;

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

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
          if (s[i][j] == '0')
            {
                int x = i;

                while (s[x][j] == '0') x--;

                int y = j;

                while (s[i][y] == '0') y--;

                g[idr[x][j]].pb(idr[i][y]);
            }

    memset(mt, -1, sizeof(mt));

    for (int i = 0; i < N; i++)
    {
        if (sz(g[i]) == 0) continue;

        memset(mk, 0, sizeof(mk));

        kuna(i);
    }

    int ans = 0;

    for (int i = 0; i < N; i++) if (mt[i] != -1) ans++;

    cout << ans << endl;
}

Subtask #1
18.0 / 18.0

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

Subtask #2
16.0 / 32.0

# Verdict Execution time Memory Grader output
1 Partially correct 10 ms 8320 KB First line is correct, but the reconstruction is not properly formatted.
2 Partially correct 10 ms 7808 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 12 ms 8192 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 11 ms 7808 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 11 ms 7808 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 10 ms 7680 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 10 ms 7552 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 12 ms 7808 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 11 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
10 Partially correct 18 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
11 Partially correct 18 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
12 Partially correct 19 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
13 Partially correct 18 ms 8576 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 18 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 18 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 18 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 16 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 16 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
19 Partially correct 18 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 16 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 18 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 18 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
23 Partially correct 18 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
24 Partially correct 14 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
25 Partially correct 18 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
26 Partially correct 17 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.

Subtask #3
30.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6272 KB Correct.
2 Correct 8 ms 6272 KB Correct.
3 Correct 8 ms 6144 KB Correct.
4 Correct 8 ms 6272 KB Correct.
5 Correct 8 ms 6272 KB Correct.
6 Correct 8 ms 6272 KB Correct.
7 Correct 8 ms 6144 KB Correct.
8 Correct 8 ms 6272 KB Correct.
9 Correct 8 ms 6144 KB Correct.
10 Correct 8 ms 6272 KB Correct.
11 Correct 8 ms 6144 KB Correct.
12 Correct 8 ms 6272 KB Correct.
13 Correct 8 ms 6272 KB Correct.
14 Correct 8 ms 6272 KB Correct.
15 Correct 9 ms 6272 KB Correct.
16 Correct 8 ms 6272 KB Correct.
17 Correct 8 ms 6272 KB Correct.
18 Correct 8 ms 6272 KB Correct.
19 Correct 8 ms 6144 KB Correct.
20 Correct 8 ms 6272 KB Correct.
21 Correct 8 ms 6272 KB Correct.
22 Correct 8 ms 6272 KB Correct.
23 Correct 8 ms 6272 KB Correct.
24 Partially correct 10 ms 8320 KB First line is correct, but the reconstruction is not properly formatted.
25 Partially correct 10 ms 7808 KB First line is correct, but the reconstruction is not properly formatted.
26 Partially correct 12 ms 8192 KB First line is correct, but the reconstruction is not properly formatted.
27 Partially correct 11 ms 7808 KB First line is correct, but the reconstruction is not properly formatted.
28 Partially correct 11 ms 7808 KB First line is correct, but the reconstruction is not properly formatted.
29 Partially correct 10 ms 7680 KB First line is correct, but the reconstruction is not properly formatted.
30 Partially correct 10 ms 7552 KB First line is correct, but the reconstruction is not properly formatted.
31 Partially correct 12 ms 7808 KB First line is correct, but the reconstruction is not properly formatted.
32 Partially correct 11 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
33 Partially correct 18 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
34 Partially correct 18 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
35 Partially correct 19 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
36 Partially correct 18 ms 8576 KB First line is correct, but the reconstruction is not properly formatted.
37 Partially correct 18 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
38 Partially correct 18 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
39 Partially correct 18 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
40 Partially correct 16 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
41 Partially correct 16 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
42 Partially correct 18 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
43 Partially correct 16 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
44 Partially correct 18 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
45 Partially correct 18 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
46 Partially correct 18 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
47 Partially correct 14 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
48 Partially correct 18 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
49 Partially correct 17 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
50 Partially correct 388 ms 10364 KB First line is correct, but the reconstruction is not properly formatted.
51 Partially correct 4787 ms 10204 KB First line is correct, but the reconstruction is not properly formatted.
52 Partially correct 410 ms 10496 KB First line is correct, but the reconstruction is not properly formatted.
53 Partially correct 387 ms 10340 KB First line is correct, but the reconstruction is not properly formatted.
54 Partially correct 333 ms 10168 KB First line is correct, but the reconstruction is not properly formatted.
55 Partially correct 452 ms 10616 KB First line is correct, but the reconstruction is not properly formatted.
56 Partially correct 406 ms 10368 KB First line is correct, but the reconstruction is not properly formatted.
57 Partially correct 403 ms 10488 KB First line is correct, but the reconstruction is not properly formatted.
58 Partially correct 3078 ms 10216 KB First line is correct, but the reconstruction is not properly formatted.
59 Partially correct 349 ms 10112 KB First line is correct, but the reconstruction is not properly formatted.
60 Partially correct 410 ms 10368 KB First line is correct, but the reconstruction is not properly formatted.
61 Partially correct 310 ms 10244 KB First line is correct, but the reconstruction is not properly formatted.
62 Partially correct 418 ms 10496 KB First line is correct, but the reconstruction is not properly formatted.
63 Partially correct 398 ms 10496 KB First line is correct, but the reconstruction is not properly formatted.
64 Partially correct 164 ms 9720 KB First line is correct, but the reconstruction is not properly formatted.
65 Partially correct 399 ms 10368 KB First line is correct, but the reconstruction is not properly formatted.
66 Partially correct 364 ms 10232 KB First line is correct, but the reconstruction is not properly formatted.
67 Partially correct 373 ms 10496 KB First line is correct, but the reconstruction is not properly formatted.
68 Partially correct 441 ms 10744 KB First line is correct, but the reconstruction is not properly formatted.
69 Partially correct 394 ms 10428 KB First line is correct, but the reconstruction is not properly formatted.
70 Partially correct 423 ms 10368 KB First line is correct, but the reconstruction is not properly formatted.
71 Partially correct 428 ms 10720 KB First line is correct, but the reconstruction is not properly formatted.
72 Partially correct 429 ms 10624 KB First line is correct, but the reconstruction is not properly formatted.
73 Partially correct 463 ms 10768 KB First line is correct, but the reconstruction is not properly formatted.
74 Partially correct 413 ms 10624 KB First line is correct, but the reconstruction is not properly formatted.
75 Partially correct 453 ms 10872 KB First line is correct, but the reconstruction is not properly formatted.