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
2017-03-04 21:52:48+0900
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
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