oj.uz

Submission #238182

# Submission time Handle Problem Language Result Execution time Memory
238182 2020-06-10T06:55:27 Z kartel Skandi (COCI20_skandi) C++14
32 / 110
 24 ms 24440 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[2005][2005];

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 < Hor_Kol; i++)
    {
        for (j = 0; j < Hor_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
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 24 ms 24440 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
32.0 / 32.0

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

Subtask #3
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 24 ms 24440 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -