Submission #501504

#	Time	Username	Problem	Language	Result	Execution time	Memory
501504		inksamurai	Skandi (COCI20_skandi)	C++17	18 / 110	1 ms	460 KiB

Main

#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 / 18
• Subtask 2: 0 / 32
• Subtask 3: 0 / 60