Submission #1141724


Source Code Expand

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<string>
#include<stack>
#include<cstdio>
#include<cmath>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i,x) for(int i=0;i<x;i++)
#define rep1(i,x) for(int i=1;i<=x;i++)
#define rrep(i,x) for(int i=x-1;i>=0;i--)
#define rrep1(i,x) for(int i=x;i>0;i--)
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
#define mp1(a,b,c) P1(a,P(b,c))
#define mp2(a,b,c,d) P2(P(a,b),P(c,d))

const int INF=1000000000;
const int dir_4[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
const int dir_8[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};

struct X{
	int H,W;
	int a[11][11];
	bool operator ==(X y){
		rep(i,11)rep(j,11){
			if(this->a[i][j] != y.a[i][j])return false;
		}
		return true;
	}
	bool operator<(X y){
		rep(i,11)rep(j,11){
			if(this->a[i][j] < y.a[i][j])return true;
			if(this->a[i][j] > y.a[i][j])return false;
		}
		return false;
	}
	void show(){
		rep(i,11){
			rep(j,11){
				printf("%d",a[i][j]);
			}
			puts("");
		}
	}
}X_;
vector<X> X[9];

void init(){
	/*X_num[1] = 1;
	X[1][0].H = 1;
	X[1][0].W = 1;
	X[1][0].a[2][2] = 1;*/
	X[3].pb(X_); X[3][0].H = 1; X[3][0].W = 1; X[3][0].a[2][2] = 1; X[3][0].a[2][3] = 1; X[3][0].a[2][4] = 1;
	X[3].pb(X_); X[3][1].H = 1; X[3][1].W = 1; X[3][1].a[2][2] = 1; X[3][1].a[3][2] = 1; X[3][1].a[4][2] = 1;
	X[3].pb(X_); X[3][2].H = 1; X[3][2].W = 1; X[3][2].a[2][2] = 1; X[3][2].a[2][3] = 1; X[3][2].a[3][2] = 1;
	X[3].pb(X_); X[3][3].H = 1; X[3][3].W = 1; X[3][3].a[2][2] = 1; X[3][3].a[2][3] = 1; X[3][3].a[3][3] = 1;
	X[3].pb(X_); X[3][4].H = 1; X[3][4].W = 1; X[3][4].a[2][2] = 1; X[3][4].a[3][2] = 1; X[3][4].a[3][3] = 1;
	X[3].pb(X_); X[3][5].H = 1; X[3][5].W = 1; X[3][5].a[3][2] = 1; X[3][5].a[2][3] = 1; X[3][5].a[3][3] = 1;
	for(int i = 4 ; i <= 8 ; i ++){
		//cout << i << endl;
		for(int j = 0 ; j < X[i-1].size() ; j ++){
			for(int x = 1 ; x <= 9 ; x ++){
				for(int y = 1 ; y <= 9 ; y ++){
					if(X[i-1][j].a[x][y] == 1)continue;
					int t = 0;
					t += X[i-1][j].a[x+1][y];
					t += X[i-1][j].a[x-1][y];
					t += X[i-1][j].a[x][y+1];
					t += X[i-1][j].a[x][y-1];
					if(t > 0){
						X[i].pb(X_);
						if(x == 1){
							for(int u = 2 ; u <= 9 ; u ++){
								for(int v = 2 ; v <= 9 ; v ++){
									X[i][X[i].size()-1].a[u][v] = X[i-1][j].a[u-1][v];
								}
							}
							X[i][X[i].size()-1].a[2][y] = 1;
						}
						else if(y == 1){
							for(int u = 2 ; u <= 9 ; u ++){
								for(int v = 2 ; v <= 9 ; v ++){
									X[i][X[i].size()-1].a[u][v] = X[i-1][j].a[u][v-1];
								}
							}
							X[i][X[i].size()-1].a[x][2] = 1;
						}
						else {
							for(int u = 2 ; u <= 9 ; u ++){
								for(int v = 2 ; v <= 9 ; v ++){
									X[i][X[i].size()-1].a[u][v] = X[i-1][j].a[u][v];
								}
							}
							X[i][X[i].size()-1].a[x][y] = 1;
						}
					}
				}
			}
		}
		sor(X[i]);
		uniq(X[i]);
		/*cout << X[i].size() << endl;
		if(i == 4)rep(j,X[i].size()){
			X[i][j].show();
		}*/
	}
	rep(i,X[8].size()){
		rep(j,11)rep(k,11){
			if(j<9 && k<9){
				X[8][i].a[j][k] = X[8][i].a[j+2][k+2];
			}
			else X[8][i].a[j][k] = 0;
			if(X[8][i].a[j][k] == 1){
				X[8][i].H = max ( X[8][i].H , j );
				X[8][i].W = max ( X[8][i].W , k );
			}
		}
		X[8][i].H ++;
		X[8][i].W ++;
		/*if(i%100 == 0){
			cout << X[8][i].H << " " << X[8][i].W << endl;
			X[8][i].show();
		}*/
	}
	//cout << X[8].size()  << endl;
}

int main(){
	init();
	
	int h,w_,k;
	string s[52];
	scanf("%d%d%d",&h,&w_,&k);
	rep(i,h)cin >> s[i];
	
	int ret = 0;
	vector<int> ans_x,ans_y;
	
	vector<P2> vec;
	rep(i,X[8].size()){
		for(int x = 0 ; x+X[8][i].H-1 < 50 ; x ++){
			for(int y = 0 ; y+X[8][i].W-1 < 50 ; y ++){
				int a = 1;
				rep(z,X[8][i].H)rep(w,X[8][i].W){
					if(X[8][i].a[z][w] == 1)a *= s[x+z][y+w]-'0';
				}
				vec.pb(mp2(a,i,x,y));
			}
		}
	}
	sor(vec);
	rev(vec);
	
	bool used[52][52];
	rep(i,52)rep(j,52)used[i][j] = false;
	rep(i,vec.size()){
		//if(i%20000 == 0)cerr << i << endl;
		P2 p = vec[i];
		bool t = true;
		rep(z,X[8][p.fr.sc].H)rep(w,X[8][p.fr.sc].W){
			if(X[8][p.fr.sc].a[z][w] == 1 && used[p.sc.fr+z][p.sc.sc+w])t = false;
		}
		if(t){
			ret ++;
			rep(z,X[8][p.fr.sc].H)rep(w,X[8][p.fr.sc].W){
				if(X[8][p.fr.sc].a[z][w] == 1){
					ans_x.pb(p.sc.fr+z);
					ans_y.pb(p.sc.sc+w);
					used[p.sc.fr+z][p.sc.sc+w] = true;
				}
			}
		}
	}
	
	
	/*rep(i,16)rep(j,16){
		vector<P1> vec;
		rep(x,3)rep(y,3)vec.pb(mp1(s[i*3+x][j*3+y]-'0',x,y));
		sor(vec);
		ret ++;
		rep(x,3)rep(y,3){
			if(vec[0].sc.fr == x && vec[0].sc.sc == y)continue;
			ans_x.pb(i*3+x);
			ans_y.pb(j*3+y);
		}
	}*/
	
	cout << ret << endl;
	rep(i,ret*8){
		printf("%d %d\n",ans_x[i]+1,ans_y[i]+1);
	}
}

Submission Info

Submission Time
Task A - Multiple Pieces
User yokozuna57
Language C++14 (GCC 5.4.1)
Score 944462
Code Size 5291 Byte
Status AC
Exec Time 1363 ms
Memory 145000 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:151:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&h,&w_,&k);
                           ^

Judge Result

Set Name test_01 test_02 test_03 test_04 test_05 test_06 test_07 test_08 test_09 test_10
Score / Max Score 95085 / 1343058 89857 / 1343058 97320 / 1343058 90113 / 1343058 102205 / 1343058 90634 / 1343058 98087 / 1343058 87391 / 1343058 98740 / 1343058 95030 / 1343058
Status
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
Set Name Test Cases
test_01 subtask_01_01.txt
test_02 subtask_01_02.txt
test_03 subtask_01_03.txt
test_04 subtask_01_04.txt
test_05 subtask_01_05.txt
test_06 subtask_01_06.txt
test_07 subtask_01_07.txt
test_08 subtask_01_08.txt
test_09 subtask_01_09.txt
test_10 subtask_01_10.txt
Case Name Status Exec Time Memory
subtask_01_01.txt AC 1330 ms 144488 KB
subtask_01_02.txt AC 1353 ms 142184 KB
subtask_01_03.txt AC 1349 ms 143080 KB
subtask_01_04.txt AC 1335 ms 144488 KB
subtask_01_05.txt AC 1359 ms 143720 KB
subtask_01_06.txt AC 1342 ms 145000 KB
subtask_01_07.txt AC 1363 ms 142312 KB
subtask_01_08.txt AC 1302 ms 142696 KB
subtask_01_09.txt AC 1339 ms 142824 KB
subtask_01_10.txt AC 1351 ms 143592 KB