oj.uz

Submission #220642

# Submission time Handle Problem Language Result Execution time Memory
220642 2020-04-08T10:33:41 Z Vimmer Skandi (COCI20_skandi) C++14
55 / 110
 5431 ms 23536 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];

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;

                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) continue;

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

        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 13 ms 13312 KB Correct.
3 Partially correct 16 ms 13312 KB First line is correct, but the reconstruction is not.
4 Correct 13 ms 13312 KB Correct.
5 Correct 14 ms 13360 KB Correct.
6 Correct 13 ms 13312 KB Correct.
7 Correct 13 ms 13312 KB Correct.
8 Correct 13 ms 13312 KB Correct.
9 Correct 14 ms 13312 KB Correct.
10 Correct 13 ms 13312 KB Correct.
11 Correct 13 ms 13312 KB Correct.
12 Correct 16 ms 13312 KB Correct.
13 Correct 14 ms 13312 KB Correct.
14 Correct 14 ms 13312 KB Correct.
15 Correct 14 ms 13312 KB Correct.
16 Correct 13 ms 13312 KB Correct.
17 Correct 14 ms 13312 KB Correct.
18 Correct 16 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 14244 KB Correct.
2 Partially correct 14 ms 13696 KB First line is correct, but the reconstruction is not.
3 Partially correct 17 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 16 ms 13696 KB First line is correct, but the reconstruction is not.
6 Partially correct 16 ms 13440 KB First line is correct, but the reconstruction is not.
7 Partially correct 15 ms 13440 KB First line is correct, but the reconstruction is not.
8 Partially correct 17 ms 13696 KB First line is correct, but the reconstruction is not.
9 Partially correct 15 ms 14464 KB First line is correct, but the reconstruction is not.
10 Partially correct 24 ms 14516 KB First line is correct, but the reconstruction is not.
11 Partially correct 23 ms 14464 KB First line is correct, but the reconstruction is not.
12 Partially correct 30 ms 14464 KB First line is correct, but the reconstruction is not.
13 Partially correct 25 ms 14464 KB First line is correct, but the reconstruction is not.
14 Partially correct 35 ms 14464 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 33 ms 14464 KB First line is correct, but the reconstruction is not.
17 Partially correct 22 ms 14464 KB First line is correct, but the reconstruction is not.
18 Partially correct 23 ms 14464 KB First line is correct, but the reconstruction is not.
19 Partially correct 26 ms 14464 KB First line is correct, but the reconstruction is not.
20 Partially correct 21 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 24 ms 14464 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 18 ms 14464 KB First line is correct, but the reconstruction is not.
25 Partially correct 29 ms 14464 KB First line is correct, but the reconstruction is not.
26 Partially correct 33 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 13 ms 13312 KB Correct.
3 Partially correct 16 ms 13312 KB First line is correct, but the reconstruction is not.
4 Correct 13 ms 13312 KB Correct.
5 Correct 14 ms 13360 KB Correct.
6 Correct 13 ms 13312 KB Correct.
7 Correct 13 ms 13312 KB Correct.
8 Correct 13 ms 13312 KB Correct.
9 Correct 14 ms 13312 KB Correct.
10 Correct 13 ms 13312 KB Correct.
11 Correct 13 ms 13312 KB Correct.
12 Correct 16 ms 13312 KB Correct.
13 Correct 14 ms 13312 KB Correct.
14 Correct 14 ms 13312 KB Correct.
15 Correct 14 ms 13312 KB Correct.
16 Correct 13 ms 13312 KB Correct.
17 Correct 14 ms 13312 KB Correct.
18 Correct 16 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 14244 KB Correct.
25 Partially correct 14 ms 13696 KB First line is correct, but the reconstruction is not.
26 Partially correct 17 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 16 ms 13696 KB First line is correct, but the reconstruction is not.
29 Partially correct 16 ms 13440 KB First line is correct, but the reconstruction is not.
30 Partially correct 15 ms 13440 KB First line is correct, but the reconstruction is not.
31 Partially correct 17 ms 13696 KB First line is correct, but the reconstruction is not.
32 Partially correct 15 ms 14464 KB First line is correct, but the reconstruction is not.
33 Partially correct 24 ms 14516 KB First line is correct, but the reconstruction is not.
34 Partially correct 23 ms 14464 KB First line is correct, but the reconstruction is not.
35 Partially correct 30 ms 14464 KB First line is correct, but the reconstruction is not.
36 Partially correct 25 ms 14464 KB First line is correct, but the reconstruction is not.
37 Partially correct 35 ms 14464 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 33 ms 14464 KB First line is correct, but the reconstruction is not.
40 Partially correct 22 ms 14464 KB First line is correct, but the reconstruction is not.
41 Partially correct 23 ms 14464 KB First line is correct, but the reconstruction is not.
42 Partially correct 26 ms 14464 KB First line is correct, but the reconstruction is not.
43 Partially correct 21 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 24 ms 14464 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 18 ms 14464 KB First line is correct, but the reconstruction is not.
48 Partially correct 29 ms 14464 KB First line is correct, but the reconstruction is not.
49 Partially correct 33 ms 14464 KB First line is correct, but the reconstruction is not.
50 Partially correct 489 ms 21104 KB First line is correct, but the reconstruction is not.
51 Partially correct 5431 ms 21664 KB First line is correct, but the reconstruction is not.
52 Partially correct 500 ms 22768 KB First line is correct, but the reconstruction is not.
53 Partially correct 490 ms 21100 KB First line is correct, but the reconstruction is not.
54 Partially correct 449 ms 21616 KB First line is correct, but the reconstruction is not.
55 Partially correct 569 ms 22252 KB First line is correct, but the reconstruction is not.
56 Partially correct 529 ms 21616 KB First line is correct, but the reconstruction is not.
57 Partially correct 540 ms 21492 KB First line is correct, but the reconstruction is not.
58 Partially correct 3471 ms 21560 KB First line is correct, but the reconstruction is not.
59 Partially correct 464 ms 20976 KB First line is correct, but the reconstruction is not.
60 Partially correct 528 ms 21740 KB First line is correct, but the reconstruction is not.
61 Partially correct 419 ms 21872 KB First line is correct, but the reconstruction is not.
62 Partially correct 530 ms 21744 KB First line is correct, but the reconstruction is not.
63 Partially correct 535 ms 21868 KB First line is correct, but the reconstruction is not.
64 Partially correct 165 ms 20728 KB First line is correct, but the reconstruction is not.
65 Partially correct 509 ms 21744 KB First line is correct, but the reconstruction is not.
66 Partially correct 449 ms 22124 KB First line is correct, but the reconstruction is not.
67 Partially correct 482 ms 23148 KB First line is correct, but the reconstruction is not.
68 Partially correct 545 ms 22764 KB First line is correct, but the reconstruction is not.
69 Partially correct 492 ms 21488 KB First line is correct, but the reconstruction is not.
70 Partially correct 512 ms 21616 KB First line is correct, but the reconstruction is not.
71 Partially correct 564 ms 23536 KB First line is correct, but the reconstruction is not.
72 Partially correct 539 ms 22124 KB First line is correct, but the reconstruction is not.
73 Partially correct 602 ms 23152 KB First line is correct, but the reconstruction is not.
74 Partially correct 546 ms 23404 KB First line is correct, but the reconstruction is not.
75 Partially correct 609 ms 23152 KB First line is correct, but the reconstruction is not.