Submission #776644

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
776644	2023-07-08T06:28:50 Z	vjudge1	Sajam (COCI18_sajam)	C++17	90 / 90	43 ms	5136 KB

sajam

#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n"
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define N 1005

bitset<N> arr[N];
int dist[N][N];
const int INF = 2e9 + 7;

int32_t main(){
	#ifndef ONLINE_JUDGE
	//fileio();
	#endif
	fastio();

	int n, k;
	cin>>n>>k;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){
			char c;
			cin>>c;
			arr[i][j] = c == 'x';
		}
	}

	for (int i = 1; i <= n; i++){
		for (int j = i + 1; j <= n; j++){
			bitset<N> tmp = arr[i] ^ arr[j];
			dist[i][j] = dist[j][i] = tmp.count();
		}
	}

	int ans = INF;
	for (int i = 1; i <= n; i++){
		int curr = 0;
		for (int j = 1; j <= n; j++){
			curr += min(dist[i][j], n - dist[i][j]);
		}
		ans = min(ans, curr);
	}

	for (int i = 1; i <= n; i++){
		int curr = 1;
		for (int j = 2; j <= n; j++){
			if (arr[j][i] == arr[1][i]) dist[1][j]++;
			else dist[1][j]--;
			curr += min(dist[1][j], n - dist[1][j]);
			if (arr[j][i] == arr[1][i]) dist[1][j]--;
			else dist[1][j]++;
		}
		ans = min(ans, curr);
	}
	if (ans <= k) cout<<"DA\n";
	else cout<<"NE\n";
	cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	468 KB	Output is correct
2	Correct	7 ms	2044 KB	Output is correct
3	Correct	11 ms	2412 KB	Output is correct
4	Correct	32 ms	4020 KB	Output is correct
5	Correct	11 ms	2388 KB	Output is correct
6	Correct	7 ms	1664 KB	Output is correct
7	Correct	11 ms	2344 KB	Output is correct
8	Correct	37 ms	3984 KB	Output is correct
9	Correct	3 ms	1236 KB	Output is correct
10	Correct	38 ms	4052 KB	Output is correct

Subtask #2

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	468 KB	Output is correct
2	Correct	1 ms	596 KB	Output is correct
3	Correct	1 ms	596 KB	Output is correct
4	Correct	1 ms	460 KB	Output is correct
5	Correct	1 ms	596 KB	Output is correct
6	Correct	1 ms	596 KB	Output is correct
7	Correct	1 ms	588 KB	Output is correct
8	Correct	1 ms	468 KB	Output is correct
9	Correct	1 ms	596 KB	Output is correct
10	Correct	1 ms	596 KB	Output is correct

Subtask #3

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	3284 KB	Output is correct
2	Correct	27 ms	3600 KB	Output is correct
3	Correct	18 ms	3088 KB	Output is correct
4	Correct	17 ms	2900 KB	Output is correct
5	Correct	31 ms	3984 KB	Output is correct
6	Correct	12 ms	2516 KB	Output is correct
7	Correct	21 ms	3340 KB	Output is correct
8	Correct	23 ms	3412 KB	Output is correct
9	Correct	8 ms	1876 KB	Output is correct
10	Correct	42 ms	4236 KB	Output is correct

Subtask #4

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	3772 KB	Output is correct
2	Correct	29 ms	3800 KB	Output is correct
3	Correct	17 ms	2964 KB	Output is correct
4	Correct	22 ms	3208 KB	Output is correct
5	Correct	28 ms	3412 KB	Output is correct
6	Correct	37 ms	4196 KB	Output is correct
7	Correct	9 ms	2260 KB	Output is correct
8	Correct	21 ms	3156 KB	Output is correct
9	Correct	25 ms	3396 KB	Output is correct
10	Correct	43 ms	4308 KB	Output is correct

Subtask #5

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	2964 KB	Output is correct
2	Correct	17 ms	2976 KB	Output is correct
3	Correct	38 ms	4304 KB	Output is correct
4	Correct	12 ms	2772 KB	Output is correct
5	Correct	19 ms	3584 KB	Output is correct
6	Correct	36 ms	5136 KB	Output is correct
7	Correct	11 ms	2648 KB	Output is correct
8	Correct	13 ms	2900 KB	Output is correct
9	Correct	15 ms	2900 KB	Output is correct
10	Correct	14 ms	2900 KB	Output is correct

Subtask #6

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	41 ms	4380 KB	Output is correct
2	Correct	37 ms	4284 KB	Output is correct
3	Correct	34 ms	4024 KB	Output is correct
4	Correct	21 ms	3796 KB	Output is correct
5	Correct	21 ms	3796 KB	Output is correct
6	Correct	30 ms	4052 KB	Output is correct
7	Correct	12 ms	2824 KB	Output is correct
8	Correct	31 ms	4628 KB	Output is correct
9	Correct	19 ms	3236 KB	Output is correct
10	Correct	40 ms	5096 KB	Output is correct