oj.uz

Submission #263494

# Submission time Handle Problem Language Result Execution time Memory
263494 2020-08-13T17:57:45 Z kingfran1907 Sajam (COCI18_sajam) C++14
30 / 90
 5000 ms 2304 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];
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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 896 KB Output is correct
3 Correct 2 ms 1152 KB Output is correct
4 Correct 6 ms 2048 KB Output is correct
5 Correct 2 ms 1152 KB Output is correct
6 Correct 2 ms 768 KB Output is correct
7 Correct 2 ms 1024 KB Output is correct
8 Correct 6 ms 2176 KB Output is correct
9 Correct 1 ms 640 KB Output is correct
10 Correct 6 ms 2176 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 8 ms 384 KB Output is correct
7 Correct 25 ms 384 KB Output is correct
8 Correct 7 ms 384 KB Output is correct
9 Correct 13 ms 384 KB Output is correct
10 Correct 11 ms 512 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1664 KB Output is correct
2 Correct 5 ms 1792 KB Output is correct
3 Correct 3 ms 1408 KB Output is correct
4 Correct 3 ms 1408 KB Output is correct
5 Correct 5 ms 2048 KB Output is correct
6 Correct 4410 ms 1200 KB Output is correct
7 Execution timed out 5072 ms 1664 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 1920 KB Output is correct
2 Correct 277 ms 2168 KB Output is correct
3 Correct 154 ms 1436 KB Output is correct
4 Correct 4 ms 1536 KB Output is correct
5 Correct 4 ms 1664 KB Output is correct
6 Execution timed out 5085 ms 2176 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 1528 KB Output is correct
2 Correct 3 ms 1408 KB Output is correct
3 Correct 889 ms 2304 KB Output is correct
4 Correct 20 ms 1152 KB Output is correct
5 Correct 116 ms 1408 KB Output is correct
6 Execution timed out 5028 ms 2176 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2304 KB Output is correct
2 Correct 1403 ms 2276 KB Output is correct
3 Correct 672 ms 2168 KB Output is correct
4 Correct 146 ms 1536 KB Output is correct
5 Correct 294 ms 1656 KB Output is correct
6 Execution timed out 5072 ms 1664 KB Time limit exceeded
7 Halted 0 ms 0 KB -