Submission #92196

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
92196	2019-01-01T22:02:28 Z	Shtef	Sajam (COCI18_sajam)	C++14	90 / 90	490 ms	668 KB

sajam

#include <iostream>
#include <bitset>
#include <algorithm>

using namespace std;

int n, k;
bitset <1005> a[1005], b[1005];

int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
for(int i = 0 ; i < n ; ++i){
	string s;
	cin >> s;
	for(int j = 0 ; j < n ; ++j){
		a[i][j] = (s[j] == 'o');
		b[i][j] = a[i][j] ^ 1;
	}
}
for(int i = 0 ; i < n ; ++i){
	int br = 0;
	for(int j = 0 ; j < n ; ++j){
		if(i == j)
			continue;
		int t1 = (a[i] ^ a[j]).count();
		int t2 = (a[i] ^ b[j]).count();
		int t3 = (b[i] ^ a[j]).count();
		int t4 = (b[i] ^ b[j]).count();
		br += min(t1, min(t2, min(t3, t4)));
	}
	if(br <= k){
		cout << "DA" << endl;
		return 0;
	}
}
if(k < n){
	cout << "NE" << endl;
	return 0;
}
for(int i = 0 ; i < n ; ++i){
	a[0][i] = a[0][i] ^ 1;
	b[0][i] = b[0][i] ^ 1;
	int br = 1;
	for(int j = 0 ; j < n ; ++j){
		if(i == j)
			continue;
		int t1 = (a[0] ^ a[j]).count();
		int t2 = (a[0] ^ b[j]).count();
		int t3 = (b[0] ^ a[j]).count();
		int t4 = (b[0] ^ b[j]).count();
		br += min(t1, min(t2, min(t3, t4)));
	}
	if(br <= k){
		cout << "DA" << endl;
		return 0;
	}
	a[0][i] = a[0][i] ^ 1;
	b[0][i] = b[0][i] ^ 1;
}
cout << "NE" << endl;

return 0;
}

Subtask #1

15.0 / 15.0

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

Subtask #2

15.0 / 15.0

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

Subtask #3

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	504 KB	Output is correct
2	Correct	5 ms	632 KB	Output is correct
3	Correct	4 ms	504 KB	Output is correct
4	Correct	4 ms	504 KB	Output is correct
5	Correct	5 ms	632 KB	Output is correct
6	Correct	78 ms	504 KB	Output is correct
7	Correct	146 ms	504 KB	Output is correct
8	Correct	160 ms	504 KB	Output is correct
9	Correct	45 ms	504 KB	Output is correct
10	Correct	273 ms	632 KB	Output is correct

Subtask #4

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	504 KB	Output is correct
2	Correct	5 ms	632 KB	Output is correct
3	Correct	3 ms	504 KB	Output is correct
4	Correct	4 ms	504 KB	Output is correct
5	Correct	4 ms	504 KB	Output is correct
6	Correct	250 ms	656 KB	Output is correct
7	Correct	61 ms	504 KB	Output is correct
8	Correct	141 ms	504 KB	Output is correct
9	Correct	154 ms	616 KB	Output is correct
10	Correct	278 ms	632 KB	Output is correct

Subtask #5

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	504 KB	Output is correct
2	Correct	4 ms	504 KB	Output is correct
3	Correct	392 ms	628 KB	Output is correct
4	Correct	145 ms	504 KB	Output is correct
5	Correct	146 ms	632 KB	Output is correct
6	Correct	490 ms	632 KB	Output is correct
7	Correct	147 ms	632 KB	Output is correct
8	Correct	167 ms	632 KB	Output is correct
9	Correct	176 ms	532 KB	Output is correct
10	Correct	166 ms	528 KB	Output is correct

Subtask #6

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	668 KB	Output is correct
2	Correct	6 ms	632 KB	Output is correct
3	Correct	355 ms	632 KB	Output is correct
4	Correct	301 ms	508 KB	Output is correct
5	Correct	147 ms	576 KB	Output is correct
6	Correct	296 ms	504 KB	Output is correct
7	Correct	159 ms	520 KB	Output is correct
8	Correct	406 ms	612 KB	Output is correct
9	Correct	216 ms	504 KB	Output is correct
10	Correct	488 ms	632 KB	Output is correct