Submission #518704

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
518704	2022-01-24T12:59:15 Z	inksamurai	Sajam (COCI18_sajam)	C++17	45 / 90	4485 ms	9020 KB

sajam

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define crep(i,x,n) for(int i=x;i<n;i++)
#define drep(i,n) for(int i=n-1;i>=0;i--)
#define vec(...) vector<__VA_ARGS__>
#define _343tk3a ios::sync_with_stdio(0),cin.tie(0)
using namespace std;
void print(){cout<<"\n";}
template<class te,class ...ti>
void print(const te&v,const ti&...nv){cout<<v;if(sizeof...(nv)){cout<<" ";print(nv...);}}
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
//e

int main(){
_343tk3a;
	int n,k;
	cin>>n>>k;
	int h,w;
	h=n,w=n;
	vec(vi) a(h,vi(w));
	rep(i,h){
		string s;
		cin>>s;
		rep(j,w){
			a[i][j]=(s[j]=='x');
		}
	}
	vec(vi) oa;
	oa=a;
	auto af=[&](vi _a){
		a=oa;
		rep(j,w){
			if(_a[j]){
				rep(_i,h){
					a[_i][j]^=1;
				}
			}
		}
		int res=0;
		rep(i,h){
			int c=0;
			rep(j,w)c+=a[i][j];
			res+=min(c,n-c);
		}
		return res;
	};
	int res=n+1;
	rep(i,h){
		res=min(res,af(a[i]));
		rep(j,w)a[i][j]^=1;
		if(res==2){
			print(i,"\n");
			break;
		}
		res=min(res,af(a[i]));
		rep(j,w)a[i][j]^=1;
	}
	print((res<=k?"DA":"NE"),"\n");
//
	return 0;
}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	317 ms	1720 KB	Output is correct
3	Correct	584 ms	2436 KB	Output is correct
4	Correct	3447 ms	6916 KB	Output is correct
5	Correct	615 ms	2464 KB	Output is correct
6	Correct	140 ms	1100 KB	Output is correct
7	Correct	533 ms	2276 KB	Output is correct
8	Correct	3569 ms	7988 KB	Output is correct
9	Correct	45 ms	720 KB	Output is correct
10	Correct	3549 ms	8244 KB	Output is correct

Subtask #2

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	2 ms	332 KB	Output is correct
3	Incorrect	3 ms	332 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #3

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1711 ms	4772 KB	Output is correct
2	Correct	2346 ms	5812 KB	Output is correct
3	Correct	1260 ms	3980 KB	Output is correct
4	Correct	1040 ms	3532 KB	Output is correct
5	Correct	3092 ms	6740 KB	Output is correct
6	Correct	628 ms	2508 KB	Output is correct
7	Correct	1650 ms	5220 KB	Output is correct
8	Correct	1899 ms	5648 KB	Output is correct
9	Correct	261 ms	1872 KB	Output is correct
10	Correct	4212 ms	9016 KB	Output is correct

Subtask #4

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2731 ms	6280 KB	Output is correct
2	Correct	2612 ms	6128 KB	Output is correct
3	Correct	1100 ms	3660 KB	Output is correct
4	Correct	1587 ms	4580 KB	Output is correct
5	Correct	1811 ms	4892 KB	Output is correct
6	Correct	4035 ms	7716 KB	Output is correct
7	Correct	436 ms	2248 KB	Output is correct
8	Correct	1508 ms	4944 KB	Output is correct
9	Correct	1749 ms	5424 KB	Output is correct
10	Correct	4209 ms	9020 KB	Output is correct

Subtask #5

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1127 ms	3660 KB	Output is correct
2	Correct	1138 ms	3692 KB	Output is correct
3	Incorrect	4211 ms	7972 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #6

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4485 ms	8224 KB	Output is correct
2	Correct	4070 ms	8732 KB	Output is correct
3	Incorrect	3424 ms	8056 KB	Output isn't correct
4	Halted	0 ms	0 KB	-