답안 #220660

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
220660	2020-04-08T11:17:50 Z	Vimmer	Skandi (COCI20_skandi)	C++14	55 / 110	5253 ms	23920 KB

skandi

#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], was[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;

                was[v] = 1;

                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 || was[i]) continue;

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

        was[i] = 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

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	13312 KB	Correct.
2	Correct	14 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	14 ms	13312 KB	Correct.
8	Correct	13 ms	13312 KB	Correct.
9	Correct	13 ms	13312 KB	Correct.
10	Correct	13 ms	13312 KB	Correct.
11	Correct	15 ms	13312 KB	Correct.
12	Correct	14 ms	13312 KB	Correct.
13	Correct	13 ms	13312 KB	Correct.
14	Correct	13 ms	13312 KB	Correct.
15	Correct	13 ms	13312 KB	Correct.
16	Correct	13 ms	13312 KB	Correct.
17	Correct	13 ms	13312 KB	Correct.
18	Correct	14 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

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	14208 KB	Correct.
2	Partially correct	14 ms	13696 KB	First line is correct, but the reconstruction is not.
3	Partially correct	16 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	15 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	18 ms	13696 KB	First line is correct, but the reconstruction is not.
8	Partially correct	16 ms	13696 KB	First line is correct, but the reconstruction is not.
9	Partially correct	16 ms	14464 KB	First line is correct, but the reconstruction is not.
10	Partially correct	25 ms	14464 KB	First line is correct, but the reconstruction is not.
11	Partially correct	24 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	24 ms	14464 KB	First line is correct, but the reconstruction is not.
14	Partially correct	24 ms	14592 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	25 ms	14464 KB	First line is correct, but the reconstruction is not.
17	Partially correct	23 ms	14464 KB	First line is correct, but the reconstruction is not.
18	Partially correct	22 ms	14464 KB	First line is correct, but the reconstruction is not.
19	Partially correct	24 ms	14464 KB	First line is correct, but the reconstruction is not.
20	Partially correct	22 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	25 ms	14592 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	14592 KB	First line is correct, but the reconstruction is not.
25	Partially correct	23 ms	14464 KB	First line is correct, but the reconstruction is not.
26	Partially correct	25 ms	14464 KB	First line is correct, but the reconstruction is not.

Subtask #3
30.0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	13312 KB	Correct.
2	Correct	14 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	14 ms	13312 KB	Correct.
8	Correct	13 ms	13312 KB	Correct.
9	Correct	13 ms	13312 KB	Correct.
10	Correct	13 ms	13312 KB	Correct.
11	Correct	15 ms	13312 KB	Correct.
12	Correct	14 ms	13312 KB	Correct.
13	Correct	13 ms	13312 KB	Correct.
14	Correct	13 ms	13312 KB	Correct.
15	Correct	13 ms	13312 KB	Correct.
16	Correct	13 ms	13312 KB	Correct.
17	Correct	13 ms	13312 KB	Correct.
18	Correct	14 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	14208 KB	Correct.
25	Partially correct	14 ms	13696 KB	First line is correct, but the reconstruction is not.
26	Partially correct	16 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	15 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	18 ms	13696 KB	First line is correct, but the reconstruction is not.
31	Partially correct	16 ms	13696 KB	First line is correct, but the reconstruction is not.
32	Partially correct	16 ms	14464 KB	First line is correct, but the reconstruction is not.
33	Partially correct	25 ms	14464 KB	First line is correct, but the reconstruction is not.
34	Partially correct	24 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	24 ms	14464 KB	First line is correct, but the reconstruction is not.
37	Partially correct	24 ms	14592 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	25 ms	14464 KB	First line is correct, but the reconstruction is not.
40	Partially correct	23 ms	14464 KB	First line is correct, but the reconstruction is not.
41	Partially correct	22 ms	14464 KB	First line is correct, but the reconstruction is not.
42	Partially correct	24 ms	14464 KB	First line is correct, but the reconstruction is not.
43	Partially correct	22 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	25 ms	14592 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	14592 KB	First line is correct, but the reconstruction is not.
48	Partially correct	23 ms	14464 KB	First line is correct, but the reconstruction is not.
49	Partially correct	25 ms	14464 KB	First line is correct, but the reconstruction is not.
50	Partially correct	472 ms	21488 KB	First line is correct, but the reconstruction is not.
51	Partially correct	5253 ms	21968 KB	First line is correct, but the reconstruction is not.
52	Partially correct	532 ms	23280 KB	First line is correct, but the reconstruction is not.
53	Partially correct	501 ms	21616 KB	First line is correct, but the reconstruction is not.
54	Partially correct	465 ms	22144 KB	First line is correct, but the reconstruction is not.
55	Partially correct	554 ms	22788 KB	First line is correct, but the reconstruction is not.
56	Partially correct	505 ms	22128 KB	First line is correct, but the reconstruction is not.
57	Partially correct	521 ms	22256 KB	First line is correct, but the reconstruction is not.
58	Partially correct	3535 ms	22108 KB	First line is correct, but the reconstruction is not.
59	Partially correct	441 ms	21232 KB	First line is correct, but the reconstruction is not.
60	Partially correct	516 ms	22268 KB	First line is correct, but the reconstruction is not.
61	Partially correct	394 ms	22252 KB	First line is correct, but the reconstruction is not.
62	Partially correct	533 ms	22240 KB	First line is correct, but the reconstruction is not.
63	Partially correct	520 ms	22632 KB	First line is correct, but the reconstruction is not.
64	Partially correct	166 ms	21240 KB	First line is correct, but the reconstruction is not.
65	Partially correct	532 ms	22128 KB	First line is correct, but the reconstruction is not.
66	Partially correct	459 ms	22636 KB	First line is correct, but the reconstruction is not.
67	Partially correct	481 ms	23664 KB	First line is correct, but the reconstruction is not.
68	Partially correct	573 ms	23148 KB	First line is correct, but the reconstruction is not.
69	Partially correct	527 ms	21872 KB	First line is correct, but the reconstruction is not.
70	Partially correct	525 ms	22000 KB	First line is correct, but the reconstruction is not.
71	Partially correct	569 ms	23920 KB	First line is correct, but the reconstruction is not.
72	Partially correct	586 ms	22632 KB	First line is correct, but the reconstruction is not.
73	Partially correct	590 ms	23660 KB	First line is correct, but the reconstruction is not.
74	Partially correct	567 ms	23852 KB	First line is correct, but the reconstruction is not.
75	Partially correct	623 ms	23696 KB	First line is correct, but the reconstruction is not.

답안 #220660

Compilation message

Subtask #1 9.0 / 18.0

Subtask #2 16.0 / 32.0

Subtask #3 30.0 / 60.0

Subtask #1
9.0 / 18.0

Subtask #2
16.0 / 32.0

Subtask #3
30.0 / 60.0