Submission #263500

#	Time	Username	Problem	Language	Result	Execution time	Memory
263500		kingfran1907	Sajam (COCI18_sajam)	C++14	90 / 90	2300 ms	2552 KiB

sajam

#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 (stderr)

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