oj.uz

Submission #501504

# Submission time Handle Problem Language Result Execution time Memory
501504 2022-01-03T14:17:26 Z inksamurai Skandi (COCI20_skandi) C++17
18 / 110
 1 ms 460 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#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 _3qplfh5 ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
using tpii=pair<int,pair<int,int>>;
using pii=pair<int,int>;
using vi=vector<int>;
using vll=vector<long long>;
 
int main(){
_3qplfh5;
	int h,w;
	cin>>h>>w;
	vec(vi) a(h,vi(w));
	rep(i,h){
		string s;
		cin>>s;
		rep(j,w){
			a[i][j]=(s[j]=='1');
		}
	}

	vec(pii) rbts;
	rep(i,h){
		rep(j,w){
			if(a[i][j]){
				if(i+1<h and !a[i+1][j]) rbts.pb({1,i*w+j});
				if(j+1<w and !a[i][j+1]) rbts.pb({0,i*w+j});
			}
		}
	}
	int n=sz(rbts);

	assert(n<=20);
	
	int ans=1e8,pmsk=-1;
	rep(msk,(1<<n)){
		vec(vec(vi)) fill(2,vec(vi)(h,vi(w)));
		rep(i,n){
			int x=rbts[i].se/w,y=rbts[i].se%w;
			int t=rbts[i].fi;
			if(msk&(1<<i)){
				if(t==1) fill[1][x+1][y]=1;
				else fill[0][x][y+1]=1;
			}
		}
		vec(vi) nea(h,vi(w));
		rep(i,h){
			rep(j,w){
				if(fill[0][i][j] or fill[1][i][j]) nea[i][j]=1;
				if(a[i][j]){
					nea[i][j]=1;
				}else{
					if(i and fill[1][i-1][j]){
						fill[1][i][j]=1;
						nea[i][j]=1;
					}
					if(j and fill[0][i][j-1]){
						fill[0][i][j]=1;
						nea[i][j]=1;
					}
				}
			}
		}
		bool pok=1;
		rep(i,h)rep(j,w){
			if(!nea[i][j]){
				pok=0;
				break;
			}
		}
		if(pok){
			int blt=__builtin_popcount(msk);
			if(blt<ans){
				ans=blt;
				pmsk=msk;
			}
		}
	}
	printf("%d\n", ans);
	rep(i,n){
		int x=rbts[i].se/w,y=rbts[i].se%w;
		int t=rbts[i].fi;
		if(pmsk&(1<<i)){
			printf("%d %d %s\n", x+1,y+1,(t==0?"DESNO":"DOLJE"));
		}
	}
//	
	return 0;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Correct.
2 Correct 0 ms 204 KB Correct.
3 Correct 1 ms 204 KB Correct.
4 Correct 1 ms 312 KB Correct.
5 Correct 1 ms 204 KB Correct.
6 Correct 1 ms 204 KB Correct.
7 Correct 0 ms 204 KB Correct.
8 Correct 0 ms 204 KB Correct.
9 Correct 0 ms 204 KB Correct.
10 Correct 0 ms 204 KB Correct.
11 Correct 1 ms 204 KB Correct.
12 Correct 0 ms 204 KB Correct.
13 Correct 1 ms 204 KB Correct.
14 Correct 0 ms 308 KB Correct.
15 Correct 1 ms 308 KB Correct.
16 Correct 0 ms 204 KB Correct.
17 Correct 0 ms 204 KB Correct.
18 Correct 1 ms 204 KB Correct.
19 Correct 1 ms 204 KB Correct.
20 Correct 1 ms 204 KB Correct.
21 Correct 0 ms 204 KB Correct.
22 Correct 1 ms 204 KB Correct.
23 Correct 1 ms 204 KB Correct.

Subtask #2
0.0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Correct.
2 Correct 0 ms 204 KB Correct.
3 Correct 1 ms 204 KB Correct.
4 Correct 1 ms 312 KB Correct.
5 Correct 1 ms 204 KB Correct.
6 Correct 1 ms 204 KB Correct.
7 Correct 0 ms 204 KB Correct.
8 Correct 0 ms 204 KB Correct.
9 Correct 0 ms 204 KB Correct.
10 Correct 0 ms 204 KB Correct.
11 Correct 1 ms 204 KB Correct.
12 Correct 0 ms 204 KB Correct.
13 Correct 1 ms 204 KB Correct.
14 Correct 0 ms 308 KB Correct.
15 Correct 1 ms 308 KB Correct.
16 Correct 0 ms 204 KB Correct.
17 Correct 0 ms 204 KB Correct.
18 Correct 1 ms 204 KB Correct.
19 Correct 1 ms 204 KB Correct.
20 Correct 1 ms 204 KB Correct.
21 Correct 0 ms 204 KB Correct.
22 Correct 1 ms 204 KB Correct.
23 Correct 1 ms 204 KB Correct.
24 Runtime error 1 ms 460 KB Execution killed with signal 6
25 Halted 0 ms 0 KB -