제출 #501348

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
501348		inksamurai	Skandi (COCI20_skandi)	C++17	0 / 110	1 ms	424 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');
		}
	}
	vi rbts;
	rep(i,h){
		rep(j,w){
			if(a[i][j]){
				rbts.pb(i*w+j);
			}
		}
	}
	int n=sz(rbts);
	assert(n<15);
	int mi=1e9;
	vec(tpii) pans;
	rep(msk,(1<<n)){
		vec(vi) nea;
		nea=a;
		int now=0;
		vec(tpii) nevc;
		rep(i,n){
			int x=rbts[i]/w,y=rbts[i]%w;
			bool pok=0;
			if(msk&(1<<i)){
				while(x+1<h){
					x++;
					if(nea[x][y]) break;
					pok=1;
					now++;
					nea[x][y]=1;
				}
			}else{
				while(y+1<w){
					y++;
					if(nea[x][y]) break;
					pok=1;
					now++;
					nea[x][y]=1;
				}
			}
			if(pok){
				nevc.pb({msk&(1<<i),{x,y}});
			}
		}
		bool gok=1;
		rep(i,h){
			rep(j,w)if(!nea[i][j])gok=0;
		}
		if(now<mi and gok){
			mi=now;
			pans=nevc;
		}
	}
	cout<<sz(pans)<<"\n";
	for(auto p : pans){
		cout<<p.se.fi+1<<" "<<p.se.se+1<<" ";
		if(p.fi==0){
			cout<<"DESNO\n";
		}else{
			cout<<"DOLJE\n";
		}
	}
//	
	return 0;
}

• Subtask 1: 0 / 18
• Subtask 2: 0 / 32
• Subtask 3: 0 / 60