oj.uz

Submission #238184

# Submission time Handle Problem Language Result Execution time Memory
238184 2020-06-10T06:57:59 Z kartel Skandi (COCI20_skandi) C++14
110 / 110
 3632 ms 24712 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#define F first
#define S second
#define pb push_back
#define N +500500
#define MaxS N * N
#define M ll(1e9 + 7)
#define sz(x) (int)x.size()
//#define re return
#define oo ll(1e18)
#define el '\n'
#define pii pair <int, int>
using namespace std;
//using namespace __gnu_pbds;
//typedef tree <int, null_type, less_equal <int> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef long double ld;

pair <int, int> Hor[N], Ver[N];
vector <int> g[N];
map <pair <int, int>, int> Ver_Id, Hor_Id;
int Hor_Kol, Ver_Kol, i, j, n, m, ans, mV[N], mH[N];
bool mk[N], mkV[N], mkH[N];
char c[505][505];

int kuhn(int v)
{
    if (mk[v]) return 0;
    mk[v] = 1;

    for (auto u : g[v])
    {
        if (mH[u] == -1 || kuhn(mH[u]))
        {
            mH[u] = v;
            return 1;
        }
    }
    return 0;
}

void dfs(int v)
{
    mkV[v] = 1;
    for (auto u : g[v])
    {
        if (mkH[u]) continue;
        mkH[u] = 1;

        dfs(mH[u]);
    }
}

int main()
{
    srand(time(0));
    ios_base::sync_with_stdio(0);
    iostream::sync_with_stdio(0);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

//    in("input.txt");
//    out("output.txt");

    cin >> n >> m;
    for (i = 1; i <= n; i++)
      for (j = 1; j <= m; j++)
        cin >> c[i][j];

    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
    {
        if (c[i][j] == '0') continue;

        if (i + 1 <= n && c[i + 1][j] == '0')
        {
            Ver_Id[{i, j}] = Ver_Kol;
            Ver[Ver_Kol++] = {i, j};
        }

        if (j + 1 <= m && c[i][j + 1] == '0')
        {
            Hor_Id[{i, j}] = Hor_Kol;
            Hor[Hor_Kol++] = {i, j};
        }
    }

    for (i = 1; i <= n; i++)
       for (j = 1; j <= m; j++)
    {
        if (c[i][j] == '1') continue;

        int I = i, J = j;

        while (I >= 0 && c[I][j] == '0') I--;

        while (J >= 0 && c[i][J] == '0') J--;

        g[Ver_Id[{I, j}]].pb(Hor_Id[{i, J}]);
    }

    for (i = 0; i < Hor_Kol; i++) mH[i] = -1, mkH[i] = 0;
    for (i = 0; i < Ver_Kol; i++) mV[i] = -1, mkV[i] = 0;

    ans = 0;
    for (i = 0; i < Ver_Kol; i++)
    {
        for (j = 0; j < Ver_Kol; j++) mk[j] = 0;

        ans += kuhn(i);
    }

    cout << ans << el;

    for (i = 0; i < Hor_Kol; i++)
        if (mH[i] != -1)
            mV[mH[i]] = i;

    for (i = 0; i < Ver_Kol; i++)
    {
        if (mV[i] != -1) continue;

        dfs(i);
    }


    for (i = 0; i < Ver_Kol; i++)
        if (!mkV[i])
           cout << Ver[i].F << " " << Ver[i].S << " DOLJE" << el;

    for (i = 0; i < Hor_Kol; i++)
        if (mkH[i])
           cout << Hor[i].F << " " << Hor[i].S << " DESNO" << el;

}

//  x ^ 2 + y ^ 2 = 1
//  x * a_i + y * b_i
//  a_i = -b_i * tan(alpha)
//  a_i / -b_i = tan(alpha)
//  alpha = atan(a_i / (-b_i))

Subtask #1
18.0 / 18.0

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

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12416 KB Correct.
2 Correct 13 ms 12416 KB Correct.
3 Correct 12 ms 12416 KB Correct.
4 Correct 11 ms 12288 KB Correct.
5 Correct 14 ms 12288 KB Correct.
6 Correct 11 ms 12160 KB Correct.
7 Correct 11 ms 12160 KB Correct.
8 Correct 11 ms 12288 KB Correct.
9 Correct 12 ms 12416 KB Correct.
10 Correct 12 ms 12544 KB Correct.
11 Correct 13 ms 12672 KB Correct.
12 Correct 14 ms 12544 KB Correct.
13 Correct 12 ms 12672 KB Correct.
14 Correct 14 ms 12672 KB Correct.
15 Correct 12 ms 12544 KB Correct.
16 Correct 12 ms 12672 KB Correct.
17 Correct 12 ms 12544 KB Correct.
18 Correct 14 ms 12544 KB Correct.
19 Correct 13 ms 12544 KB Correct.
20 Correct 12 ms 12544 KB Correct.
21 Correct 13 ms 12672 KB Correct.
22 Correct 14 ms 12800 KB Correct.
23 Correct 12 ms 12672 KB Correct.
24 Correct 14 ms 12544 KB Correct.
25 Correct 12 ms 12544 KB Correct.
26 Correct 13 ms 12544 KB Correct.

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12160 KB Correct.
2 Correct 11 ms 12160 KB Correct.
3 Correct 11 ms 12160 KB Correct.
4 Correct 11 ms 12160 KB Correct.
5 Correct 11 ms 12160 KB Correct.
6 Correct 11 ms 12160 KB Correct.
7 Correct 11 ms 12160 KB Correct.
8 Correct 11 ms 12160 KB Correct.
9 Correct 12 ms 12160 KB Correct.
10 Correct 11 ms 12160 KB Correct.
11 Correct 13 ms 12160 KB Correct.
12 Correct 11 ms 12160 KB Correct.
13 Correct 11 ms 12160 KB Correct.
14 Correct 11 ms 12160 KB Correct.
15 Correct 11 ms 12160 KB Correct.
16 Correct 12 ms 12160 KB Correct.
17 Correct 15 ms 12160 KB Correct.
18 Correct 11 ms 12160 KB Correct.
19 Correct 12 ms 12160 KB Correct.
20 Correct 12 ms 12160 KB Correct.
21 Correct 11 ms 12160 KB Correct.
22 Correct 12 ms 12160 KB Correct.
23 Correct 12 ms 12160 KB Correct.
24 Correct 11 ms 12416 KB Correct.
25 Correct 13 ms 12416 KB Correct.
26 Correct 12 ms 12416 KB Correct.
27 Correct 11 ms 12288 KB Correct.
28 Correct 14 ms 12288 KB Correct.
29 Correct 11 ms 12160 KB Correct.
30 Correct 11 ms 12160 KB Correct.
31 Correct 11 ms 12288 KB Correct.
32 Correct 12 ms 12416 KB Correct.
33 Correct 12 ms 12544 KB Correct.
34 Correct 13 ms 12672 KB Correct.
35 Correct 14 ms 12544 KB Correct.
36 Correct 12 ms 12672 KB Correct.
37 Correct 14 ms 12672 KB Correct.
38 Correct 12 ms 12544 KB Correct.
39 Correct 12 ms 12672 KB Correct.
40 Correct 12 ms 12544 KB Correct.
41 Correct 14 ms 12544 KB Correct.
42 Correct 13 ms 12544 KB Correct.
43 Correct 12 ms 12544 KB Correct.
44 Correct 13 ms 12672 KB Correct.
45 Correct 14 ms 12800 KB Correct.
46 Correct 12 ms 12672 KB Correct.
47 Correct 14 ms 12544 KB Correct.
48 Correct 12 ms 12544 KB Correct.
49 Correct 13 ms 12544 KB Correct.
50 Correct 154 ms 22624 KB Correct.
51 Correct 3632 ms 16504 KB Correct.
52 Correct 184 ms 22928 KB Correct.
53 Correct 158 ms 22668 KB Correct.
54 Correct 153 ms 21472 KB Correct.
55 Correct 202 ms 24056 KB Correct.
56 Correct 169 ms 23420 KB Correct.
57 Correct 190 ms 23160 KB Correct.
58 Correct 2334 ms 15640 KB Correct.
59 Correct 145 ms 21856 KB Correct.
60 Correct 174 ms 23264 KB Correct.
61 Correct 153 ms 20344 KB Correct.
62 Correct 175 ms 23416 KB Correct.
63 Correct 176 ms 23536 KB Correct.
64 Correct 151 ms 13740 KB Correct.
65 Correct 180 ms 23288 KB Correct.
66 Correct 166 ms 21496 KB Correct.
67 Correct 185 ms 21660 KB Correct.
68 Correct 197 ms 24068 KB Correct.
69 Correct 167 ms 22904 KB Correct.
70 Correct 173 ms 22988 KB Correct.
71 Correct 204 ms 23648 KB Correct.
72 Correct 182 ms 24184 KB Correct.
73 Correct 212 ms 24508 KB Correct.
74 Correct 211 ms 23448 KB Correct.
75 Correct 223 ms 24712 KB Correct.