oj.uz

Submission #105131

# Submission time Handle Problem Language Result Execution time Memory
105131 2019-04-10T16:24:30 Z arthur_nascimento Sajam (COCI18_sajam) C++14
90 / 90
 322 ms 6484 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 1010
#define bs bitset<maxn>
#define debug 
int ans = 0;

bs col[maxn];

char M[maxn][maxn];

int dif[maxn][maxn];

void go(int n,int k){

	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			col[j].set(i,M[i][j] == 'x');
	
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			dif[i][j] = (col[i] ^ col[j]).count();
			
	for(int j=0;j<n;j++){
		
		int s = 0;
		
		for(int jj=0;jj<n;jj++)
			s += min(dif[j][jj],n-dif[j][jj]);
			
		if(s <= k)
			ans = 1;
	
	}
	debug("%d\n",ans);
}

int main(){

	int n,k;
	scanf("%d%d",&n,&k);
	
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			scanf(" %c",&M[i][j]);
		
	go(n,k);
	
	for(int i=0;i<n;i++)
		for(int j=i;j<n;j++)
			swap(M[i][j], M[j][i]);
			
	go(n,k);
		
	for(int i=0;i<n;i++){
		
		int s = 1;
		for(int j=1;j<n;j++){
			int d = dif[0][j];
			if(M[i][0] == M[i][j])
				d++;
			else
				d--;
			s += min(d,n-d);
		}
		
		if(s <= k){
			ans = 1;
			debug("i %d s %d\n",i,s);
		}
	
	}
	
	if(ans)
		printf("DA\n");
	else
		printf("NE\n");
		
}

Compilation message

sajam.cpp: In function 'void go(int, int)':
sajam.cpp:36:15: warning: left operand of comma operator has no effect [-Wunused-value]
  debug("%d\n",ans);
               ^~~
sajam.cpp: In function 'int main()':
sajam.cpp:70:24: warning: left operand of comma operator has no effect [-Wunused-value]
    debug("i %d s %d\n",i,s);
                        ^
sajam.cpp:70:26: warning: right operand of comma operator has no effect [-Wunused-value]
    debug("i %d s %d\n",i,s);
                          ^
sajam.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&k);
  ~~~~~^~~~~~~~~~~~~~
sajam.cpp:46:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf(" %c",&M[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 512 KB Output is correct
2 Correct 48 ms 2680 KB Output is correct
3 Correct 65 ms 3320 KB Output is correct
4 Correct 251 ms 5752 KB Output is correct
5 Correct 60 ms 3328 KB Output is correct
6 Correct 29 ms 2176 KB Output is correct
7 Correct 69 ms 3228 KB Output is correct
8 Correct 272 ms 5984 KB Output is correct
9 Correct 16 ms 1536 KB Output is correct
10 Correct 219 ms 5988 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 640 KB Output is correct
2 Correct 3 ms 668 KB Output is correct
3 Correct 4 ms 768 KB Output is correct
4 Correct 3 ms 640 KB Output is correct
5 Correct 4 ms 640 KB Output is correct
6 Correct 3 ms 640 KB Output is correct
7 Correct 5 ms 768 KB Output is correct
8 Correct 3 ms 640 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 3 ms 640 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 4736 KB Output is correct
2 Correct 164 ms 5212 KB Output is correct
3 Correct 99 ms 4344 KB Output is correct
4 Correct 132 ms 3996 KB Output is correct
5 Correct 175 ms 5624 KB Output is correct
6 Correct 69 ms 3356 KB Output is correct
7 Correct 118 ms 4804 KB Output is correct
8 Correct 134 ms 4936 KB Output is correct
9 Correct 35 ms 2552 KB Output is correct
10 Correct 204 ms 6236 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 5484 KB Output is correct
2 Correct 174 ms 5496 KB Output is correct
3 Correct 111 ms 4088 KB Output is correct
4 Correct 163 ms 4516 KB Output is correct
5 Correct 120 ms 4808 KB Output is correct
6 Correct 213 ms 6080 KB Output is correct
7 Correct 52 ms 2936 KB Output is correct
8 Correct 182 ms 4472 KB Output is correct
9 Correct 163 ms 4728 KB Output is correct
10 Correct 263 ms 6264 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 3960 KB Output is correct
2 Correct 86 ms 4048 KB Output is correct
3 Correct 242 ms 6392 KB Output is correct
4 Correct 91 ms 3448 KB Output is correct
5 Correct 102 ms 4140 KB Output is correct
6 Correct 201 ms 6188 KB Output is correct
7 Correct 65 ms 3320 KB Output is correct
8 Correct 76 ms 3580 KB Output is correct
9 Correct 103 ms 3576 KB Output is correct
10 Correct 90 ms 3604 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 6484 KB Output is correct
2 Correct 322 ms 6264 KB Output is correct
3 Correct 252 ms 6008 KB Output is correct
4 Correct 119 ms 4600 KB Output is correct
5 Correct 129 ms 4604 KB Output is correct
6 Correct 115 ms 4744 KB Output is correct
7 Correct 66 ms 3412 KB Output is correct
8 Correct 212 ms 5496 KB Output is correct
9 Correct 106 ms 4080 KB Output is correct
10 Correct 217 ms 6192 KB Output is correct