oj.uz

Submission #220641

# Submission time Handle Problem Language Result Execution time Memory
220641 2020-04-08T10:33:16 Z Vimmer Skandi (COCI20_skandi) C++14
55 / 110
 5353 ms 23280 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 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 13 ms 13312 KB Correct.
8 Correct 14 ms 13312 KB Correct.
9 Correct 13 ms 13312 KB Correct.
10 Correct 13 ms 13312 KB Correct.
11 Correct 13 ms 13312 KB Correct.
12 Correct 14 ms 13312 KB Correct.
13 Partially correct 13 ms 13312 KB First line is correct, but the reconstruction is not.
14 Partially correct 14 ms 13312 KB First line is correct, but the reconstruction is not.
15 Partially correct 13 ms 13312 KB First line is correct, but the reconstruction is not.
16 Correct 13 ms 13312 KB Correct.
17 Correct 14 ms 13312 KB Correct.
18 Correct 13 ms 13312 KB Correct.
19 Partially correct 13 ms 13312 KB First line is correct, but the reconstruction is not.
20 Correct 13 ms 13312 KB Correct.
21 Correct 13 ms 13312 KB Correct.
22 Correct 14 ms 13312 KB Correct.
23 Correct 13 ms 13312 KB Correct.

Subtask #2
16.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14208 KB Correct.
2 Correct 14 ms 13696 KB Correct.
3 Correct 16 ms 14080 KB Correct.
4 Correct 14 ms 13696 KB Correct.
5 Partially correct 16 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 14 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 Correct 15 ms 14464 KB Correct.
10 Partially correct 24 ms 14464 KB First line is correct, but the reconstruction is not.
11 Partially correct 25 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 25 ms 14592 KB First line is correct, but the reconstruction is not.
14 Partially correct 24 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 23 ms 14464 KB First line is correct, but the reconstruction is not.
17 Partially correct 26 ms 14464 KB First line is correct, but the reconstruction is not.
18 Partially correct 21 ms 14464 KB First line is correct, but the reconstruction is not.
19 Partially correct 23 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 24 ms 14464 KB First line is correct, but the reconstruction is not.
22 Partially correct 25 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 19 ms 14464 KB First line is correct, but the reconstruction is not.
25 Partially correct 25 ms 14464 KB First line is correct, but the reconstruction is not.
26 Partially correct 24 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 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 13 ms 13312 KB Correct.
8 Correct 14 ms 13312 KB Correct.
9 Correct 13 ms 13312 KB Correct.
10 Correct 13 ms 13312 KB Correct.
11 Correct 13 ms 13312 KB Correct.
12 Correct 14 ms 13312 KB Correct.
13 Partially correct 13 ms 13312 KB First line is correct, but the reconstruction is not.
14 Partially correct 14 ms 13312 KB First line is correct, but the reconstruction is not.
15 Partially correct 13 ms 13312 KB First line is correct, but the reconstruction is not.
16 Correct 13 ms 13312 KB Correct.
17 Correct 14 ms 13312 KB Correct.
18 Correct 13 ms 13312 KB Correct.
19 Partially correct 13 ms 13312 KB First line is correct, but the reconstruction is not.
20 Correct 13 ms 13312 KB Correct.
21 Correct 13 ms 13312 KB Correct.
22 Correct 14 ms 13312 KB Correct.
23 Correct 13 ms 13312 KB Correct.
24 Correct 15 ms 14208 KB Correct.
25 Correct 14 ms 13696 KB Correct.
26 Correct 16 ms 14080 KB Correct.
27 Correct 14 ms 13696 KB Correct.
28 Partially correct 16 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 14 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 Correct 15 ms 14464 KB Correct.
33 Partially correct 24 ms 14464 KB First line is correct, but the reconstruction is not.
34 Partially correct 25 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 25 ms 14592 KB First line is correct, but the reconstruction is not.
37 Partially correct 24 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 23 ms 14464 KB First line is correct, but the reconstruction is not.
40 Partially correct 26 ms 14464 KB First line is correct, but the reconstruction is not.
41 Partially correct 21 ms 14464 KB First line is correct, but the reconstruction is not.
42 Partially correct 23 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 24 ms 14464 KB First line is correct, but the reconstruction is not.
45 Partially correct 25 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 19 ms 14464 KB First line is correct, but the reconstruction is not.
48 Partially correct 25 ms 14464 KB First line is correct, but the reconstruction is not.
49 Partially correct 24 ms 14464 KB First line is correct, but the reconstruction is not.
50 Partially correct 493 ms 21104 KB First line is correct, but the reconstruction is not.
51 Partially correct 5353 ms 21552 KB First line is correct, but the reconstruction is not.
52 Partially correct 508 ms 22896 KB First line is correct, but the reconstruction is not.
53 Partially correct 488 ms 21356 KB First line is correct, but the reconstruction is not.
54 Partially correct 452 ms 21608 KB First line is correct, but the reconstruction is not.
55 Partially correct 571 ms 22380 KB First line is correct, but the reconstruction is not.
56 Partially correct 516 ms 21736 KB First line is correct, but the reconstruction is not.
57 Partially correct 502 ms 21488 KB First line is correct, but the reconstruction is not.
58 Partially correct 3478 ms 21656 KB First line is correct, but the reconstruction is not.
59 Partially correct 451 ms 21060 KB First line is correct, but the reconstruction is not.
60 Partially correct 507 ms 21748 KB First line is correct, but the reconstruction is not.
61 Partially correct 430 ms 22000 KB First line is correct, but the reconstruction is not.
62 Partially correct 531 ms 21744 KB First line is correct, but the reconstruction is not.
63 Partially correct 535 ms 21740 KB First line is correct, but the reconstruction is not.
64 Partially correct 177 ms 20732 KB First line is correct, but the reconstruction is not.
65 Partially correct 520 ms 21740 KB First line is correct, but the reconstruction is not.
66 Partially correct 447 ms 22176 KB First line is correct, but the reconstruction is not.
67 Partially correct 484 ms 23128 KB First line is correct, but the reconstruction is not.
68 Partially correct 580 ms 22448 KB First line is correct, but the reconstruction is not.
69 Partially correct 531 ms 21572 KB First line is correct, but the reconstruction is not.
70 Partially correct 541 ms 21592 KB First line is correct, but the reconstruction is not.
71 Partially correct 560 ms 23260 KB First line is correct, but the reconstruction is not.
72 Partially correct 591 ms 22140 KB First line is correct, but the reconstruction is not.
73 Partially correct 629 ms 23148 KB First line is correct, but the reconstruction is not.
74 Partially correct 563 ms 23280 KB First line is correct, but the reconstruction is not.
75 Partially correct 644 ms 22976 KB First line is correct, but the reconstruction is not.