oj.uz

Submission #263500

# Submission time Handle Problem Language Result Execution time Memory
263500 2020-08-13T18:07:40 Z kingfran1907 Sajam (COCI18_sajam) C++14
90 / 90
 2300 ms 2552 KB 
#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;
typedef long long llint;

const int maxn = 1010;
const int base = 31337;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const int logo = 20;
const int off = 1 << logo;
const int treesiz = off << 1;

int n, k;
char niz[maxn][maxn];
bitset< maxn > b[maxn];
int pr[maxn];
bool flag[maxn];

int main() {
	srand(time(0));
	scanf("%d%d", &n, &k);
	for (int i = 0; i < n; i++) {
		scanf("%s", niz+i);
	}
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (niz[i][j] == 'o') b[i][j] = 1;
			else b[i][j] = 0;
		}
	}
	
	if (k == 0) {
		memset(flag, false, sizeof flag);
		for (int i = 0; i < n; i++) {
			if (niz[0][i] == 'o') flag[i] = true;
		}
		
		bool ac = true;
		for (int i = 0; i < n; i++) {
			int cnt = 0;
			for (int j = 0; j < n; j++) {
				cnt += ((niz[i][j] == 'o') + flag[j]) % 2;
			}
			if (cnt > 0 && cnt < n) ac = false;
		}
		
		if (ac) printf("DA\n");
		else printf("NE\n");
		return 0;
	}
	
	for (int i = 0; i < n; i++) pr[i] = i;
	random_shuffle(pr, pr+n);
	
	for (int ab = 0; ab < min(30, n); ab++) {
		int tren = pr[ab];
		
		for (int i = 0; i < n; i++) {
			if (niz[tren][i] == 'o') flag[i] = true;
			else flag[i] = false;
		}
		
		int ac = 0;
		for (int i = 0; i < n; i++) {
			int x = 0;
			for (int j = 0; j < n; j++) {
				x += ((niz[i][j] == 'o') + flag[j]) % 2;
			}
			ac += min(x, n - x);
		}
		if (ac <= k) {
			printf("DA\n");
			return 0;
		}
		
		for (int a = 0; a < n; a++) {
			b[tren][a] = 1 - b[tren][a];
			
			int ac = 0;
			for (int i = 0; i < n; i++) {
				int x = (b[tren] ^ b[i]).count();
				ac += min(x, n - x);
			}
			if (ac <= k - 1) {
				printf("DA\n");
				return 0;
			}
			
			b[tren][a] = 1 - b[tren][a];
 		}
	}
	printf("NE\n");
	return 0;
}

Compilation message

sajam.cpp: In function 'int main()':
sajam.cpp:26:11: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[1010]' [-Wformat=]
   26 |   scanf("%s", niz+i);
      |          ~^   ~~~~~
      |           |      |
      |           char*  char (*)[1010]
sajam.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   24 |  scanf("%d%d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~
sajam.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   26 |   scanf("%s", niz+i);
      |   ~~~~~^~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 2 ms 768 KB Output is correct
3 Correct 3 ms 896 KB Output is correct
4 Correct 8 ms 1280 KB Output is correct
5 Correct 3 ms 896 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 4 ms 896 KB Output is correct
8 Correct 11 ms 1408 KB Output is correct
9 Correct 1 ms 672 KB Output is correct
10 Correct 11 ms 1408 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 10 ms 384 KB Output is correct
7 Correct 18 ms 384 KB Output is correct
8 Correct 8 ms 384 KB Output is correct
9 Correct 14 ms 384 KB Output is correct
10 Correct 11 ms 384 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 1152 KB Output is correct
2 Correct 6 ms 1280 KB Output is correct
3 Correct 5 ms 1024 KB Output is correct
4 Correct 4 ms 1056 KB Output is correct
5 Correct 8 ms 1280 KB Output is correct
6 Correct 674 ms 976 KB Output is correct
7 Correct 1299 ms 1208 KB Output is correct
8 Correct 1507 ms 1912 KB Output is correct
9 Correct 393 ms 896 KB Output is correct
10 Correct 2276 ms 2552 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1280 KB Output is correct
2 Correct 26 ms 1336 KB Output is correct
3 Correct 4 ms 1056 KB Output is correct
4 Correct 5 ms 1152 KB Output is correct
5 Correct 17 ms 1152 KB Output is correct
6 Correct 2236 ms 1460 KB Output is correct
7 Correct 570 ms 1124 KB Output is correct
8 Correct 1290 ms 1664 KB Output is correct
9 Correct 1359 ms 1796 KB Output is correct
10 Correct 2300 ms 2452 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1152 KB Output is correct
2 Correct 17 ms 1152 KB Output is correct
3 Correct 61 ms 1536 KB Output is correct
4 Correct 16 ms 1024 KB Output is correct
5 Correct 11 ms 1152 KB Output is correct
6 Correct 2230 ms 1576 KB Output is correct
7 Correct 659 ms 1152 KB Output is correct
8 Correct 742 ms 1280 KB Output is correct
9 Correct 776 ms 1280 KB Output is correct
10 Correct 799 ms 1280 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 1536 KB Output is correct
2 Correct 54 ms 1536 KB Output is correct
3 Correct 50 ms 1536 KB Output is correct
4 Correct 46 ms 1280 KB Output is correct
5 Correct 41 ms 1280 KB Output is correct
6 Correct 1318 ms 1340 KB Output is correct
7 Correct 687 ms 1400 KB Output is correct
8 Correct 1829 ms 2120 KB Output is correct
9 Correct 991 ms 1516 KB Output is correct
10 Correct 2150 ms 2356 KB Output is correct