oj.uz

답안 #92196

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
92196 2019-01-01T22:02:28 Z Shtef Sajam (COCI18_sajam) C++14
90 / 90
 490 ms 668 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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