Submission #92196

#	Time	Username	Problem	Language	Result	Execution time	Memory
92196		Shtef	Sajam (COCI18_sajam)	C++14	90 / 90	490 ms	668 KiB

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 / 15
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 15 / 15