oj.uz

답안 #366426

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
366426 2021-02-14T07:34:25 Z Return_0 Skandi (COCI20_skandi) C++17
55 / 110
 188 ms 24936 KB 
#pragma GCC optimize("Ofast,unroll-loops")
// #pragma comment(linker, "/stack:200000000")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef int ll;
typedef long double ld;
typedef pair <ll, ll> pll;

#ifdef SINA
#define dbg(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1> void __f(const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << std::endl; }
template <typename Arg1, typename... Args> void __f (const char* names, Arg1&& arg1, Args&&... args) {
	const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...); }
#define dbg2(x, j, n) cout<< #x << " : "; output((j), (n), x, 1); cout.flush();
#else
#define dbg(...) 0
#define dbg2(x, j, n) 0
#endif
#define SZ(x) ((ll)((x).size()))
#define File(s, t) freopen(s ".txt", "r", stdin); freopen(t ".txt", "w", stdout);
#define input(j, n, a) for (int _i = (j); _i < (n)+(j); _i++) cin>> a[_i];
#define output(j, n, a, t) for (int _i = (j); _i < (n)+(j); _i++) cout<< a[_i] << (((t) && _i != (n)+(j)-1)? ' ' : '\n');
#define kill(x) return cout<< x << endl, 0
#define cl const ll
#define fr first
#define sc second
#define lc (v << 1)
#define rc (lc | 1)
#define mid ((l + r) >> 1)
#define All(x) (x).begin(), (x).end()

cl inf = sizeof(ll) == 4 ? (1e9 + 10) : (3e18), mod = 1e9 + 7, MOD = 998244353;

template <class A, class B> ostream& operator << (ostream& out, const pair<A, B> &a) {
	return out << '(' << a.first << ", " << a.second << ')';    }
template <class A> ostream& operator << (ostream& out, const vector<A> &a) {
	if(a.empty())return out<<"[]";out<< '[' << a[0]; for (int i = 0; ++i < (int)(a.size());)out<< ", " <<a[i];return out<<']';}
template <class T, typename _t = less <T> > using Tree = tree <T, null_type, _t, rb_tree_tag, tree_order_statistics_node_update>;

cl N = 5e2 + 3;

ll n, m, X, ans, lft [N][N], mark [N * N * 2], ptr = 2, match [N * N * 2];
char a [N][N];
vector <ll> adj [N * N * 2], lewd;

inline ll conv (cl &x, cl &y) { return (x - 1) * m + y; }

void DFS (cl &v, cl &h = 0) {
	mark[v] = 1;
	if (h)	lewd.push_back(v);
	for (auto &u : adj[v]) if (!mark[u])	DFS(u, 1 - h);
}

bool dfs (ll v) {
    mark[v] = ptr;
    for (auto u : adj[v]) if (match[u] == -1 || (mark[match[u]] != ptr && dfs(match[u]))) {
        match[v] = u, match[u] = v;
        return true;
    }
    return false;
}

void Find_Matching () {
    memset(match, -1, sizeof match);
    memset(mark, -1, sizeof mark);
	bool can_find = true; ptr = -1;
    while (can_find) {
        can_find = false, ptr++;
        for (ll v = ptr; v < SZ(lewd); v++) if (mark[lewd[v]] != ptr && match[lewd[v]] == -1) can_find |= dfs(lewd[v]);
    }
}

void force (cl &v, cl &tp) {
	mark[v] = tp;
	if (tp == 1) {
		if (!mark[match[v]])	force(match[v], 2);
	}
	else for (auto &u : adj[v]) if (!mark[u]) force(u, 1);
}

int main ()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin>> n >> m; X = n * m;
	for (ll i = 1; i <= n; i++)	for (ll j = 1; j <= m; j++)	cin>> a[i][j];
	for (ll i = 1, cur; i <= n; i++) for (ll j = 1; j <= m; j++) {
		if (a[i][j] - '0')	cur = conv(i, j);
		else lft[i][j] = cur;
	}
	for (ll j = 1, cur; j <= m; j++) for (ll i = 1; i <= n; i++) {
		if (a[i][j] - '0')	cur = conv(i, j) + X;
		else adj[lft[i][j]].push_back(cur), adj[cur].push_back(lft[i][j]);
	}

	for (ll v = 1; v <= X + X; v++)	if (!mark[v])	DFS(v);

	Find_Matching();

	memset(mark, 0, sizeof mark);
	for (ll v = 1; v <= X + X; v++) {
		if (match[v] < 1)	force(v, 2);
		else	ans++;
	}

	cout<< ans / 2 << '\n';
	for (ll v = 1; v <= X + X; v++) {
		if (match[v] > 0 && !mark[v])	mark[v] = 1, mark[match[v]] = 2;
		if (match[v] > 0 && mark[v] == 1) {
			if (v > X)	cout<< (v - X) / m + 1 << ' ' << ((v - X) % m ? (v - X) % m : m) << " DOLJE\n";
			else	cout<< v / m + 1 << ' ' << (v % m ? v % m : m) << " DESNO\n";
		}
	}

	return 0;
}
/*

*/

Compilation message

skandi.cpp: In function 'std::ostream& operator<<(std::ostream&, const std::vector<_Tp>&)':
skandi.cpp:44:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   44 |  if(a.empty())return out<<"[]";out<< '[' << a[0]; for (int i = 0; ++i < (int)(a.size());)out<< ", " <<a[i];return out<<']';}
      |  ^~
skandi.cpp:44:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   44 |  if(a.empty())return out<<"[]";out<< '[' << a[0]; for (int i = 0; ++i < (int)(a.size());)out<< ", " <<a[i];return out<<']';}
      |                                ^~~
skandi.cpp: In function 'int main()':
skandi.cpp:96:18: warning: 'cur' may be used uninitialized in this function [-Wmaybe-uninitialized]
   96 |   else lft[i][j] = cur;
      |        ~~~~~~~~~~^~~~~

Subtask #1
9.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 16236 KB Correct.
2 Partially correct 12 ms 16236 KB First line is correct, but the reconstruction is not properly formatted.
3 Correct 11 ms 16236 KB Correct.
4 Partially correct 11 ms 16236 KB First line is correct, but the reconstruction is not properly formatted.
5 Correct 11 ms 16236 KB Correct.
6 Correct 11 ms 16236 KB Correct.
7 Partially correct 12 ms 16228 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 11 ms 16236 KB First line is correct, but the reconstruction is not properly formatted.
9 Correct 11 ms 16236 KB Correct.
10 Partially correct 11 ms 16236 KB First line is correct, but the reconstruction is not properly formatted.
11 Correct 11 ms 16236 KB Correct.
12 Partially correct 12 ms 16236 KB First line is correct, but the reconstruction is not properly formatted.
13 Correct 11 ms 16236 KB Correct.
14 Correct 11 ms 16236 KB Correct.
15 Correct 11 ms 16236 KB Correct.
16 Correct 11 ms 16236 KB Correct.
17 Correct 11 ms 16236 KB Correct.
18 Correct 11 ms 16236 KB Correct.
19 Correct 11 ms 16236 KB Correct.
20 Correct 11 ms 16236 KB Correct.
21 Correct 11 ms 16236 KB Correct.
22 Partially correct 11 ms 16256 KB First line is correct, but the reconstruction is not properly formatted.
23 Correct 11 ms 16236 KB Correct.

Subtask #2
16.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 12 ms 16876 KB First line is correct, but the reconstruction is not properly formatted.
2 Partially correct 12 ms 16620 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 12 ms 17260 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 12 ms 16620 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 12 ms 16620 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 12 ms 16364 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 12 ms 16364 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 12 ms 16620 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 12 ms 17516 KB First line is correct, but the reconstruction is not properly formatted.
10 Partially correct 14 ms 17516 KB First line is correct, but the reconstruction is not properly formatted.
11 Partially correct 13 ms 17516 KB First line is correct, but the reconstruction is not properly formatted.
12 Partially correct 13 ms 17516 KB First line is correct, but the reconstruction is not properly formatted.
13 Partially correct 13 ms 17516 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 13 ms 17516 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 13 ms 17516 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 13 ms 17516 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 13 ms 17516 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 13 ms 17516 KB First line is correct, but the reconstruction is not properly formatted.
19 Partially correct 13 ms 17516 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 13 ms 17644 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 13 ms 17516 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 13 ms 17516 KB First line is correct, but the reconstruction is not properly formatted.
23 Partially correct 13 ms 17516 KB First line is correct, but the reconstruction is not properly formatted.
24 Partially correct 13 ms 17516 KB First line is correct, but the reconstruction is not properly formatted.
25 Partially correct 13 ms 17516 KB First line is correct, but the reconstruction is not properly formatted.
26 Partially correct 13 ms 17516 KB First line is correct, but the reconstruction is not properly formatted.

Subtask #3
30.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 16236 KB Correct.
2 Partially correct 12 ms 16236 KB First line is correct, but the reconstruction is not properly formatted.
3 Correct 11 ms 16236 KB Correct.
4 Partially correct 11 ms 16236 KB First line is correct, but the reconstruction is not properly formatted.
5 Correct 11 ms 16236 KB Correct.
6 Correct 11 ms 16236 KB Correct.
7 Partially correct 12 ms 16228 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 11 ms 16236 KB First line is correct, but the reconstruction is not properly formatted.
9 Correct 11 ms 16236 KB Correct.
10 Partially correct 11 ms 16236 KB First line is correct, but the reconstruction is not properly formatted.
11 Correct 11 ms 16236 KB Correct.
12 Partially correct 12 ms 16236 KB First line is correct, but the reconstruction is not properly formatted.
13 Correct 11 ms 16236 KB Correct.
14 Correct 11 ms 16236 KB Correct.
15 Correct 11 ms 16236 KB Correct.
16 Correct 11 ms 16236 KB Correct.
17 Correct 11 ms 16236 KB Correct.
18 Correct 11 ms 16236 KB Correct.
19 Correct 11 ms 16236 KB Correct.
20 Correct 11 ms 16236 KB Correct.
21 Correct 11 ms 16236 KB Correct.
22 Partially correct 11 ms 16256 KB First line is correct, but the reconstruction is not properly formatted.
23 Correct 11 ms 16236 KB Correct.
24 Partially correct 12 ms 16876 KB First line is correct, but the reconstruction is not properly formatted.
25 Partially correct 12 ms 16620 KB First line is correct, but the reconstruction is not properly formatted.
26 Partially correct 12 ms 17260 KB First line is correct, but the reconstruction is not properly formatted.
27 Partially correct 12 ms 16620 KB First line is correct, but the reconstruction is not properly formatted.
28 Partially correct 12 ms 16620 KB First line is correct, but the reconstruction is not properly formatted.
29 Partially correct 12 ms 16364 KB First line is correct, but the reconstruction is not properly formatted.
30 Partially correct 12 ms 16364 KB First line is correct, but the reconstruction is not properly formatted.
31 Partially correct 12 ms 16620 KB First line is correct, but the reconstruction is not properly formatted.
32 Partially correct 12 ms 17516 KB First line is correct, but the reconstruction is not properly formatted.
33 Partially correct 14 ms 17516 KB First line is correct, but the reconstruction is not properly formatted.
34 Partially correct 13 ms 17516 KB First line is correct, but the reconstruction is not properly formatted.
35 Partially correct 13 ms 17516 KB First line is correct, but the reconstruction is not properly formatted.
36 Partially correct 13 ms 17516 KB First line is correct, but the reconstruction is not properly formatted.
37 Partially correct 13 ms 17516 KB First line is correct, but the reconstruction is not properly formatted.
38 Partially correct 13 ms 17516 KB First line is correct, but the reconstruction is not properly formatted.
39 Partially correct 13 ms 17516 KB First line is correct, but the reconstruction is not properly formatted.
40 Partially correct 13 ms 17516 KB First line is correct, but the reconstruction is not properly formatted.
41 Partially correct 13 ms 17516 KB First line is correct, but the reconstruction is not properly formatted.
42 Partially correct 13 ms 17516 KB First line is correct, but the reconstruction is not properly formatted.
43 Partially correct 13 ms 17644 KB First line is correct, but the reconstruction is not properly formatted.
44 Partially correct 13 ms 17516 KB First line is correct, but the reconstruction is not properly formatted.
45 Partially correct 13 ms 17516 KB First line is correct, but the reconstruction is not properly formatted.
46 Partially correct 13 ms 17516 KB First line is correct, but the reconstruction is not properly formatted.
47 Partially correct 13 ms 17516 KB First line is correct, but the reconstruction is not properly formatted.
48 Partially correct 13 ms 17516 KB First line is correct, but the reconstruction is not properly formatted.
49 Partially correct 13 ms 17516 KB First line is correct, but the reconstruction is not properly formatted.
50 Partially correct 74 ms 21736 KB First line is correct, but the reconstruction is not properly formatted.
51 Partially correct 188 ms 21996 KB First line is correct, but the reconstruction is not properly formatted.
52 Partially correct 118 ms 24168 KB First line is correct, but the reconstruction is not properly formatted.
53 Partially correct 77 ms 21888 KB First line is correct, but the reconstruction is not properly formatted.
54 Partially correct 89 ms 23272 KB First line is correct, but the reconstruction is not properly formatted.
55 Partially correct 90 ms 22504 KB First line is correct, but the reconstruction is not properly formatted.
56 Partially correct 77 ms 22120 KB First line is correct, but the reconstruction is not properly formatted.
57 Partially correct 79 ms 22000 KB First line is correct, but the reconstruction is not properly formatted.
58 Partially correct 182 ms 21484 KB First line is correct, but the reconstruction is not properly formatted.
59 Partially correct 76 ms 21480 KB First line is correct, but the reconstruction is not properly formatted.
60 Partially correct 82 ms 22120 KB First line is correct, but the reconstruction is not properly formatted.
61 Partially correct 95 ms 23912 KB First line is correct, but the reconstruction is not properly formatted.
62 Partially correct 85 ms 22124 KB First line is correct, but the reconstruction is not properly formatted.
63 Partially correct 82 ms 22380 KB First line is correct, but the reconstruction is not properly formatted.
64 Partially correct 35 ms 19948 KB First line is correct, but the reconstruction is not properly formatted.
65 Partially correct 83 ms 22248 KB First line is correct, but the reconstruction is not properly formatted.
66 Partially correct 101 ms 24040 KB First line is correct, but the reconstruction is not properly formatted.
67 Partially correct 119 ms 24936 KB First line is correct, but the reconstruction is not properly formatted.
68 Partially correct 93 ms 22508 KB First line is correct, but the reconstruction is not properly formatted.
69 Partially correct 84 ms 21992 KB First line is correct, but the reconstruction is not properly formatted.
70 Partially correct 79 ms 21996 KB First line is correct, but the reconstruction is not properly formatted.
71 Partially correct 117 ms 24652 KB First line is correct, but the reconstruction is not properly formatted.
72 Partially correct 82 ms 22508 KB First line is correct, but the reconstruction is not properly formatted.
73 Partially correct 110 ms 23144 KB First line is correct, but the reconstruction is not properly formatted.
74 Partially correct 112 ms 24936 KB First line is correct, but the reconstruction is not properly formatted.
75 Partially correct 104 ms 22900 KB First line is correct, but the reconstruction is not properly formatted.