Submission #776642

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
776642	2023-07-08T06:27:10 Z	vjudge1	Sajam (COCI18_sajam)	C++17	45 / 90	44 ms	4364 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[i][j], n - dist[i][j]);
			if (arr[j][i] == arr[1][i]) dist[1][j]--;
			else dist[1][j]++;
		}
	}
	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	9 ms	2040 KB	Output is correct
3	Correct	13 ms	2412 KB	Output is correct
4	Correct	33 ms	3924 KB	Output is correct
5	Correct	11 ms	2440 KB	Output is correct
6	Correct	5 ms	1620 KB	Output is correct
7	Correct	10 ms	2260 KB	Output is correct
8	Correct	44 ms	3988 KB	Output is correct
9	Correct	3 ms	1236 KB	Output is correct
10	Correct	36 ms	4012 KB	Output is correct

Subtask #2

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	Incorrect	1 ms	596 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #3

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	3284 KB	Output is correct
2	Correct	32 ms	3688 KB	Output is correct
3	Correct	19 ms	3028 KB	Output is correct
4	Correct	17 ms	2900 KB	Output is correct
5	Correct	32 ms	3980 KB	Output is correct
6	Correct	12 ms	2516 KB	Output is correct
7	Correct	25 ms	3332 KB	Output is correct
8	Correct	24 ms	3468 KB	Output is correct
9	Correct	7 ms	1964 KB	Output is correct
10	Correct	40 ms	4252 KB	Output is correct

Subtask #4

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	3828 KB	Output is correct
2	Correct	30 ms	3796 KB	Output is correct
3	Correct	22 ms	2960 KB	Output is correct
4	Correct	24 ms	3316 KB	Output is correct
5	Correct	23 ms	3336 KB	Output is correct
6	Correct	37 ms	4180 KB	Output is correct
7	Correct	9 ms	2260 KB	Output is correct
8	Correct	23 ms	3252 KB	Output is correct
9	Correct	23 ms	3308 KB	Output is correct
10	Correct	39 ms	4292 KB	Output is correct

Subtask #5

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	2944 KB	Output is correct
2	Correct	17 ms	2980 KB	Output is correct
3	Incorrect	39 ms	4256 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #6

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	39 ms	4364 KB	Output is correct
2	Correct	38 ms	4180 KB	Output is correct
3	Incorrect	38 ms	4052 KB	Output isn't correct
4	Halted	0 ms	0 KB	-