Submission #263494

#	Time	Username	Problem	Language	Result	Execution time	Memory
263494		kingfran1907	Sajam (COCI18_sajam)	C++14	30 / 90	5085 ms	2304 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];
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);
	}
	
	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++) {
			niz[tren][a] = 'x' + 'o' - niz[tren][a];
			
			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 - 1) {
				printf("DA\n");
				return 0;
			}
			
			niz[tren][a] = 'x' + 'o' - niz[tren][a];
 		}
	}
	printf("NE\n");
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 15