oj.uz

Submission #220660

# Submission time Handle Problem Language Result Execution time Memory
220660 2020-04-08T11:17:50 Z Vimmer Skandi (COCI20_skandi) C++14
55 / 110
 5253 ms 23920 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];

pair <int, int> conv[505 * 505];

vector <pair <int, int> > g[N], gr[N];

bool mk[N], mkr[N], was[N];

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

    mk[v] = 1;

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

                was[v] = 1;

                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];

    int id = 0;

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

    int koler = 0;

    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], koler});

                gr[idr[i][y]].pb({idr[x][j], koler++});
            }

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

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

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

        was[i] = kuna(i);
    }

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

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

        for (auto it : g[mt[i]])
            if (!mkr[it.S]) kol++;

        for (auto it : gr[i])
            if (!mkr[it.S]) kol--;

        if (kol > 0)
        {
            for (auto it : g[mt[i]]) mkr[it.S] = 1;

            ans.pb({{conv[mt[i]]}, 1});
        }
        else
        {
            for (auto it : g[i]) mkr[it.S] = 1;

            ans.pb({{conv[i]}, 0});
        }
    }

    cout << sz(ans) << endl;

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

Subtask #1
9.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 13312 KB Correct.
2 Correct 14 ms 13312 KB Correct.
3 Partially correct 13 ms 13312 KB First line is correct, but the reconstruction is not.
4 Correct 13 ms 13312 KB Correct.
5 Correct 13 ms 13312 KB Correct.
6 Correct 13 ms 13312 KB Correct.
7 Correct 14 ms 13312 KB Correct.
8 Correct 13 ms 13312 KB Correct.
9 Correct 13 ms 13312 KB Correct.
10 Correct 13 ms 13312 KB Correct.
11 Correct 15 ms 13312 KB Correct.
12 Correct 14 ms 13312 KB Correct.
13 Correct 13 ms 13312 KB Correct.
14 Correct 13 ms 13312 KB Correct.
15 Correct 13 ms 13312 KB Correct.
16 Correct 13 ms 13312 KB Correct.
17 Correct 13 ms 13312 KB Correct.
18 Correct 14 ms 13312 KB Correct.
19 Correct 13 ms 13312 KB Correct.
20 Correct 13 ms 13312 KB Correct.
21 Correct 13 ms 13312 KB Correct.
22 Correct 14 ms 13312 KB Correct.
23 Correct 14 ms 13312 KB Correct.

Subtask #2
16.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14208 KB Correct.
2 Partially correct 14 ms 13696 KB First line is correct, but the reconstruction is not.
3 Partially correct 16 ms 14080 KB First line is correct, but the reconstruction is not.
4 Partially correct 15 ms 13696 KB First line is correct, but the reconstruction is not.
5 Partially correct 15 ms 13696 KB First line is correct, but the reconstruction is not.
6 Partially correct 15 ms 13568 KB First line is correct, but the reconstruction is not.
7 Partially correct 18 ms 13696 KB First line is correct, but the reconstruction is not.
8 Partially correct 16 ms 13696 KB First line is correct, but the reconstruction is not.
9 Partially correct 16 ms 14464 KB First line is correct, but the reconstruction is not.
10 Partially correct 25 ms 14464 KB First line is correct, but the reconstruction is not.
11 Partially correct 24 ms 14464 KB First line is correct, but the reconstruction is not.
12 Partially correct 24 ms 14464 KB First line is correct, but the reconstruction is not.
13 Partially correct 24 ms 14464 KB First line is correct, but the reconstruction is not.
14 Partially correct 24 ms 14592 KB First line is correct, but the reconstruction is not.
15 Partially correct 24 ms 14464 KB First line is correct, but the reconstruction is not.
16 Partially correct 25 ms 14464 KB First line is correct, but the reconstruction is not.
17 Partially correct 23 ms 14464 KB First line is correct, but the reconstruction is not.
18 Partially correct 22 ms 14464 KB First line is correct, but the reconstruction is not.
19 Partially correct 24 ms 14464 KB First line is correct, but the reconstruction is not.
20 Partially correct 22 ms 14464 KB First line is correct, but the reconstruction is not.
21 Partially correct 23 ms 14464 KB First line is correct, but the reconstruction is not.
22 Partially correct 25 ms 14592 KB First line is correct, but the reconstruction is not.
23 Partially correct 24 ms 14464 KB First line is correct, but the reconstruction is not.
24 Partially correct 19 ms 14592 KB First line is correct, but the reconstruction is not.
25 Partially correct 23 ms 14464 KB First line is correct, but the reconstruction is not.
26 Partially correct 25 ms 14464 KB First line is correct, but the reconstruction is not.

Subtask #3
30.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 13312 KB Correct.
2 Correct 14 ms 13312 KB Correct.
3 Partially correct 13 ms 13312 KB First line is correct, but the reconstruction is not.
4 Correct 13 ms 13312 KB Correct.
5 Correct 13 ms 13312 KB Correct.
6 Correct 13 ms 13312 KB Correct.
7 Correct 14 ms 13312 KB Correct.
8 Correct 13 ms 13312 KB Correct.
9 Correct 13 ms 13312 KB Correct.
10 Correct 13 ms 13312 KB Correct.
11 Correct 15 ms 13312 KB Correct.
12 Correct 14 ms 13312 KB Correct.
13 Correct 13 ms 13312 KB Correct.
14 Correct 13 ms 13312 KB Correct.
15 Correct 13 ms 13312 KB Correct.
16 Correct 13 ms 13312 KB Correct.
17 Correct 13 ms 13312 KB Correct.
18 Correct 14 ms 13312 KB Correct.
19 Correct 13 ms 13312 KB Correct.
20 Correct 13 ms 13312 KB Correct.
21 Correct 13 ms 13312 KB Correct.
22 Correct 14 ms 13312 KB Correct.
23 Correct 14 ms 13312 KB Correct.
24 Correct 14 ms 14208 KB Correct.
25 Partially correct 14 ms 13696 KB First line is correct, but the reconstruction is not.
26 Partially correct 16 ms 14080 KB First line is correct, but the reconstruction is not.
27 Partially correct 15 ms 13696 KB First line is correct, but the reconstruction is not.
28 Partially correct 15 ms 13696 KB First line is correct, but the reconstruction is not.
29 Partially correct 15 ms 13568 KB First line is correct, but the reconstruction is not.
30 Partially correct 18 ms 13696 KB First line is correct, but the reconstruction is not.
31 Partially correct 16 ms 13696 KB First line is correct, but the reconstruction is not.
32 Partially correct 16 ms 14464 KB First line is correct, but the reconstruction is not.
33 Partially correct 25 ms 14464 KB First line is correct, but the reconstruction is not.
34 Partially correct 24 ms 14464 KB First line is correct, but the reconstruction is not.
35 Partially correct 24 ms 14464 KB First line is correct, but the reconstruction is not.
36 Partially correct 24 ms 14464 KB First line is correct, but the reconstruction is not.
37 Partially correct 24 ms 14592 KB First line is correct, but the reconstruction is not.
38 Partially correct 24 ms 14464 KB First line is correct, but the reconstruction is not.
39 Partially correct 25 ms 14464 KB First line is correct, but the reconstruction is not.
40 Partially correct 23 ms 14464 KB First line is correct, but the reconstruction is not.
41 Partially correct 22 ms 14464 KB First line is correct, but the reconstruction is not.
42 Partially correct 24 ms 14464 KB First line is correct, but the reconstruction is not.
43 Partially correct 22 ms 14464 KB First line is correct, but the reconstruction is not.
44 Partially correct 23 ms 14464 KB First line is correct, but the reconstruction is not.
45 Partially correct 25 ms 14592 KB First line is correct, but the reconstruction is not.
46 Partially correct 24 ms 14464 KB First line is correct, but the reconstruction is not.
47 Partially correct 19 ms 14592 KB First line is correct, but the reconstruction is not.
48 Partially correct 23 ms 14464 KB First line is correct, but the reconstruction is not.
49 Partially correct 25 ms 14464 KB First line is correct, but the reconstruction is not.
50 Partially correct 472 ms 21488 KB First line is correct, but the reconstruction is not.
51 Partially correct 5253 ms 21968 KB First line is correct, but the reconstruction is not.
52 Partially correct 532 ms 23280 KB First line is correct, but the reconstruction is not.
53 Partially correct 501 ms 21616 KB First line is correct, but the reconstruction is not.
54 Partially correct 465 ms 22144 KB First line is correct, but the reconstruction is not.
55 Partially correct 554 ms 22788 KB First line is correct, but the reconstruction is not.
56 Partially correct 505 ms 22128 KB First line is correct, but the reconstruction is not.
57 Partially correct 521 ms 22256 KB First line is correct, but the reconstruction is not.
58 Partially correct 3535 ms 22108 KB First line is correct, but the reconstruction is not.
59 Partially correct 441 ms 21232 KB First line is correct, but the reconstruction is not.
60 Partially correct 516 ms 22268 KB First line is correct, but the reconstruction is not.
61 Partially correct 394 ms 22252 KB First line is correct, but the reconstruction is not.
62 Partially correct 533 ms 22240 KB First line is correct, but the reconstruction is not.
63 Partially correct 520 ms 22632 KB First line is correct, but the reconstruction is not.
64 Partially correct 166 ms 21240 KB First line is correct, but the reconstruction is not.
65 Partially correct 532 ms 22128 KB First line is correct, but the reconstruction is not.
66 Partially correct 459 ms 22636 KB First line is correct, but the reconstruction is not.
67 Partially correct 481 ms 23664 KB First line is correct, but the reconstruction is not.
68 Partially correct 573 ms 23148 KB First line is correct, but the reconstruction is not.
69 Partially correct 527 ms 21872 KB First line is correct, but the reconstruction is not.
70 Partially correct 525 ms 22000 KB First line is correct, but the reconstruction is not.
71 Partially correct 569 ms 23920 KB First line is correct, but the reconstruction is not.
72 Partially correct 586 ms 22632 KB First line is correct, but the reconstruction is not.
73 Partially correct 590 ms 23660 KB First line is correct, but the reconstruction is not.
74 Partially correct 567 ms 23852 KB First line is correct, but the reconstruction is not.
75 Partially correct 623 ms 23696 KB First line is correct, but the reconstruction is not.