oj.uz

Submission #238657

# Submission time Handle Problem Language Result Execution time Memory
238657 2020-06-12T09:18:55 Z SamAnd Skandi (COCI20_skandi) C++17
110 / 110
 1926 ms 35568 KB 
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 1003;

int n, m;
char a[N][N];

vector<int> g[N * N];

int ul[N][N], uu[N][N];

int f(int i, int j)
{
    return i * m + j;
}

int u[N * N];

bool c[N * N];
vector<int> v;
bool dfs(int x)
{
    if (c[x])
        return false;
    c[x] = true;
    v.push_back(x);
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i];
        if (u[h] == -1)
        {
            u[h] = x;
            return true;
        }
        else if (dfs(u[h]))
        {
            u[h] = x;
            return true;
        }
    }
    return false;
}

bool cc[N * N];
void dfs1(int x)
{
    c[x] = true;
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i];
        if (!c[h])
            dfs1(h);
    }
}

void solv()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i)
    {
        scanf(" %s", a[i]);
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            if (a[i][j] == '1')
                ul[i][j] = j;
            else
                ul[i][j] = ul[i][j - 1];
        }
    }
    for (int j = 0; j < m; ++j)
    {
        for (int i = 0; i < n; ++i)
        {
            if (a[i][j] == '1')
                uu[i][j] = i;
            else
                uu[i][j] = uu[i - 1][j];
        }
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            if (a[i][j] == '0')
            {
                g[f(i, ul[i][j])].push_back(f(uu[i][j], j));
            }
        }
    }
    for (int i = 0; i < n * m; ++i)
        u[i] = -1;
    for (int i = 0; i < n * m; ++i)
    {
        dfs(i);
        for (int j = 0; j < v.size(); ++j)
            c[v[j]] = false;
        v.clear();
    }
    for (int i = 0; i < n * m; ++i)
        g[i].clear();
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            if (a[i][j] == '0')
            {
                if (u[f(uu[i][j], j)] == f(i, ul[i][j]))
                    g[f(uu[i][j], j) + n * m].push_back(f(i, ul[i][j]));
                else
                    g[f(i, ul[i][j])].push_back(f(uu[i][j], j) + n * m);
            }
        }
    }
    for (int i = 0; i < n * m; ++i)
    {
        if (u[i] != -1)
            cc[u[i]] = true;
    }
    for (int i = 0; i < n * m; ++i)
    {
        if (!cc[i])
            dfs1(i);
    }
    vector<pair<pair<int, int>, char> > ans;
    for (int i = 0; i < n * m; ++i)
    {
        if (!c[i])
        {
            int x = i / m;
            int y = i % m;
            ans.push_back(m_p(m_p(x + 1, y + 1), 'R'));
        }
    }
    for (int i = n * m; i < 2 * n * m; ++i)
    {
        if (c[i])
        {
            int x = (i - n * m) / m;
            int y = (i - n * m) % m;
            ans.push_back(m_p(m_p(x + 1, y + 1), 'D'));
        }
    }
    printf("%d\n", ans.size());
    for (int i = 0; i < ans.size(); ++i)
    {
        if (ans[i].se == 'R')
            printf("%d %d DESNO\n", ans[i].fi.fi, ans[i].fi.se);
        else
            printf("%d %d DOLJE\n", ans[i].fi.fi, ans[i].fi.se);
    }
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    //ios_base::sync_with_stdio(false), cin.tie(0);
    solv();
    return 0;
}

//while ((double)clock() / CLOCKS_PER_SEC <= 0.9){}

Compilation message

skandi.cpp: In function 'bool dfs(int)':
skandi.cpp:35:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
skandi.cpp: In function 'void dfs1(int)':
skandi.cpp:56:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
skandi.cpp: In function 'void solv()':
skandi.cpp:106:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < v.size(); ++j)
                         ~~^~~~~~~~~~
skandi.cpp:154:30: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<std::pair<std::pair<int, int>, char> >::size_type {aka long unsigned int}' [-Wformat=]
     printf("%d\n", ans.size());
                    ~~~~~~~~~~^
skandi.cpp:155:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < ans.size(); ++i)
                     ~~^~~~~~~~~~~~
skandi.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
skandi.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %s", a[i]);
         ~~~~~^~~~~~~~~~~~~

Subtask #1
18.0 / 18.0

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

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 27776 KB Correct.
2 Correct 19 ms 25728 KB Correct.
3 Correct 20 ms 27136 KB Correct.
4 Correct 19 ms 25600 KB Correct.
5 Correct 19 ms 25472 KB Correct.
6 Correct 19 ms 24832 KB Correct.
7 Correct 18 ms 24704 KB Correct.
8 Correct 20 ms 25600 KB Correct.
9 Correct 24 ms 28416 KB Correct.
10 Correct 21 ms 28544 KB Correct.
11 Correct 21 ms 28544 KB Correct.
12 Correct 21 ms 28544 KB Correct.
13 Correct 21 ms 28544 KB Correct.
14 Correct 21 ms 28544 KB Correct.
15 Correct 21 ms 28544 KB Correct.
16 Correct 21 ms 28544 KB Correct.
17 Correct 22 ms 28544 KB Correct.
18 Correct 22 ms 28672 KB Correct.
19 Correct 21 ms 28544 KB Correct.
20 Correct 25 ms 28544 KB Correct.
21 Correct 21 ms 28544 KB Correct.
22 Correct 21 ms 28544 KB Correct.
23 Correct 21 ms 28544 KB Correct.
24 Correct 25 ms 28544 KB Correct.
25 Correct 22 ms 28544 KB Correct.
26 Correct 21 ms 28544 KB Correct.

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 24064 KB Correct.
2 Correct 19 ms 24064 KB Correct.
3 Correct 18 ms 24064 KB Correct.
4 Correct 19 ms 24064 KB Correct.
5 Correct 18 ms 24064 KB Correct.
6 Correct 20 ms 24192 KB Correct.
7 Correct 18 ms 24064 KB Correct.
8 Correct 19 ms 24064 KB Correct.
9 Correct 18 ms 24064 KB Correct.
10 Correct 18 ms 24064 KB Correct.
11 Correct 18 ms 24064 KB Correct.
12 Correct 18 ms 24064 KB Correct.
13 Correct 18 ms 24064 KB Correct.
14 Correct 19 ms 24064 KB Correct.
15 Correct 19 ms 24064 KB Correct.
16 Correct 18 ms 24064 KB Correct.
17 Correct 18 ms 24064 KB Correct.
18 Correct 18 ms 24064 KB Correct.
19 Correct 21 ms 24064 KB Correct.
20 Correct 18 ms 24064 KB Correct.
21 Correct 18 ms 24064 KB Correct.
22 Correct 31 ms 24064 KB Correct.
23 Correct 18 ms 24064 KB Correct.
24 Correct 20 ms 27776 KB Correct.
25 Correct 19 ms 25728 KB Correct.
26 Correct 20 ms 27136 KB Correct.
27 Correct 19 ms 25600 KB Correct.
28 Correct 19 ms 25472 KB Correct.
29 Correct 19 ms 24832 KB Correct.
30 Correct 18 ms 24704 KB Correct.
31 Correct 20 ms 25600 KB Correct.
32 Correct 24 ms 28416 KB Correct.
33 Correct 21 ms 28544 KB Correct.
34 Correct 21 ms 28544 KB Correct.
35 Correct 21 ms 28544 KB Correct.
36 Correct 21 ms 28544 KB Correct.
37 Correct 21 ms 28544 KB Correct.
38 Correct 21 ms 28544 KB Correct.
39 Correct 21 ms 28544 KB Correct.
40 Correct 22 ms 28544 KB Correct.
41 Correct 22 ms 28672 KB Correct.
42 Correct 21 ms 28544 KB Correct.
43 Correct 25 ms 28544 KB Correct.
44 Correct 21 ms 28544 KB Correct.
45 Correct 21 ms 28544 KB Correct.
46 Correct 21 ms 28544 KB Correct.
47 Correct 25 ms 28544 KB Correct.
48 Correct 22 ms 28544 KB Correct.
49 Correct 21 ms 28544 KB Correct.
50 Correct 53 ms 34036 KB Correct.
51 Correct 975 ms 32056 KB Correct.
52 Correct 62 ms 34804 KB Correct.
53 Correct 51 ms 34416 KB Correct.
54 Correct 57 ms 33392 KB Correct.
55 Correct 59 ms 35056 KB Correct.
56 Correct 59 ms 34696 KB Correct.
57 Correct 53 ms 34544 KB Correct.
58 Correct 1926 ms 32044 KB Correct.
59 Correct 52 ms 33648 KB Correct.
60 Correct 55 ms 34544 KB Correct.
61 Correct 65 ms 33648 KB Correct.
62 Correct 56 ms 34160 KB Correct.
63 Correct 56 ms 34672 KB Correct.
64 Correct 190 ms 31352 KB Correct.
65 Correct 55 ms 34672 KB Correct.
66 Correct 62 ms 33648 KB Correct.
67 Correct 78 ms 34416 KB Correct.
68 Correct 59 ms 35184 KB Correct.
69 Correct 55 ms 34416 KB Correct.
70 Correct 56 ms 34544 KB Correct.
71 Correct 66 ms 35184 KB Correct.
72 Correct 56 ms 35188 KB Correct.
73 Correct 62 ms 35440 KB Correct.
74 Correct 65 ms 35056 KB Correct.
75 Correct 61 ms 35568 KB Correct.