oj.uz

Submission #200955

# Submission time Handle Problem Language Result Execution time Memory
200955 2020-02-08T19:39:50 Z Saboon Sajam (COCI18_sajam) C++14
90 / 90
 2275 ms 2424 KB 
# include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

//# define int long long
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, int> pdi;
typedef pair<ll, ll> pll;

# define S second
# define F first
# define kill(x) return(cout << x << endl, 0LL)
# define debug(x) cerr<< #x << " = " << x << endl
# define ddebug(x, y) cerr<< #x << " = " << x  << ", " << #y << " = " << y << endl
# define tdebug(x, y, z) cerr<< #x << " = " << x  << ", " << #y << " = " << y << ", " << #z << " = " << z << endl
# define bin(x) cerr<< #x << " : " << bitset<4>(x) << endl
# define sz(s) (int)s.size()
# define sq(x) (x) * (x)
# define PB(x) push_back(x)
# define smax(x, y) (x) = max((x), (y))
# define smin(x, y) (x) = min((x), (y))
# define all(x) x.begin(), x.end()
# define SP fixed << setprecision(10)
# define MP make_pair
# define uop(x, y) pii(min(x, y), max(x, y))

const int MAXN = 1000 + 10;
bool a[MAXN][MAXN];
int sum[MAXN];

int32_t main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	int n, k;
	cin >> n >> k;

	for (int i = 0; i < n; i ++)
		for (int j = 0; j < n; j ++)
		{
			char c;
			cin >> c;
			a[i][j] = (c == 'x');
		}

	for (int x = 0; x < n; x ++)
	{
		memset(sum, 0, sizeof sum);
		for (int j = 0; j < n; j ++)
			for (int i = 0; i < n; i ++)
				sum[i] += a[i][j] ^ a[x][j];

		int s = 0;
		for (int i = 0; i < n; i ++)
			s += min(sum[i], n - sum[i]);
		if (s <= k)
			kill("DA");
	}
	if (k != n)
		kill("NE");

	for (int x = 0; x < n; x ++)
	{
		memset(sum, 0, sizeof sum);
		a[0][x] ^= 1;
		for (int j = 0; j < n; j ++)
			for (int i = 0; i < n; i ++)
				sum[i] += a[i][j] ^ a[0][j];
		a[0][x] ^= 1;

		int s = 0;
		for (int i = 0; i < n; i ++)
			s += min(sum[i], n - sum[i]);
		if (s < k)
			kill("DA");
	}
	cout << "NE" << endl;

	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 8 ms 888 KB Output is correct
3 Correct 9 ms 1148 KB Output is correct
4 Correct 20 ms 2168 KB Output is correct
5 Correct 9 ms 1144 KB Output is correct
6 Correct 7 ms 760 KB Output is correct
7 Correct 147 ms 1148 KB Output is correct
8 Correct 1004 ms 2168 KB Output is correct
9 Correct 17 ms 632 KB Output is correct
10 Correct 1008 ms 2296 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 6 ms 504 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 6 ms 376 KB Output is correct
10 Correct 6 ms 376 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1656 KB Output is correct
2 Correct 17 ms 1784 KB Output is correct
3 Correct 13 ms 1532 KB Output is correct
4 Correct 12 ms 1400 KB Output is correct
5 Correct 20 ms 2040 KB Output is correct
6 Correct 193 ms 1144 KB Output is correct
7 Correct 510 ms 1656 KB Output is correct
8 Correct 614 ms 1792 KB Output is correct
9 Correct 80 ms 888 KB Output is correct
10 Correct 1210 ms 2332 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2040 KB Output is correct
2 Correct 18 ms 1912 KB Output is correct
3 Correct 13 ms 1400 KB Output is correct
4 Correct 15 ms 1528 KB Output is correct
5 Correct 15 ms 1656 KB Output is correct
6 Correct 1126 ms 2168 KB Output is correct
7 Correct 132 ms 1144 KB Output is correct
8 Correct 481 ms 1528 KB Output is correct
9 Correct 544 ms 1784 KB Output is correct
10 Correct 1194 ms 2424 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1400 KB Output is correct
2 Correct 12 ms 1400 KB Output is correct
3 Correct 1773 ms 2424 KB Output is correct
4 Correct 322 ms 1272 KB Output is correct
5 Correct 433 ms 1400 KB Output is correct
6 Correct 2275 ms 2332 KB Output is correct
7 Correct 342 ms 1272 KB Output is correct
8 Correct 426 ms 1272 KB Output is correct
9 Correct 442 ms 1272 KB Output is correct
10 Correct 439 ms 1272 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2296 KB Output is correct
2 Correct 22 ms 2296 KB Output is correct
3 Correct 1552 ms 2040 KB Output is correct
4 Correct 936 ms 1656 KB Output is correct
5 Correct 499 ms 1532 KB Output is correct
6 Correct 1051 ms 1784 KB Output is correct
7 Correct 364 ms 1144 KB Output is correct
8 Correct 1635 ms 2040 KB Output is correct
9 Correct 647 ms 1528 KB Output is correct
10 Correct 2161 ms 2296 KB Output is correct