Submission #1140704
Source Code Expand
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;
void makePolyomino(int n, vector<vector<vector<pair<int, int> > > >& p, bool isFlip = true)
{
const int dy[] = {0, 1, 0, -1};
const int dx[] = {1, 0, -1, 0};
class Func
{
public:
static void normalize(vector<pair<int, int> >& v)
{
int n = v.size();
int y = INT_MAX;
int x = INT_MAX;
for(int i=0; i<n; ++i){
y = min(y, v[i].first);
x = min(x, v[i].second);
}
for(int i=0; i<n; ++i){
v[i].first -= y;
v[i].second -= x;
}
sort(v.begin(), v.end());
}
static void rotate(vector<pair<int, int> >& v)
{
int n = v.size();
for(int i=0; i<n; ++i){
swap(v[i].first, v[i].second);
v[i].first *= -1;
}
}
static void flip(vector<pair<int, int> >& v)
{
int n = v.size();
for(int i=0; i<n; ++i)
v[i].first *= -1;
}
};
set<vector<pair<int, int> > > s;
s.insert({make_pair(0, 0)});
for(int i=1; i<n; ++i){
set<vector<pair<int, int> > > t;
for(const auto& v : s){
for(int j=0; j<i; ++j){
for(int k=0; k<4; ++k){
auto p = make_pair(v[j].first + dy[k], v[j].second + dx[k]);
if(find(v.begin(), v.end(), p) != v.end())
continue;
auto v2 = v;
v2.push_back(p);
Func::normalize(v2);
t.insert(v2);
}
}
}
s.clear();
for(const auto& v : t){
auto v2 = v;
auto minV = v2;
for(int a=0; a<(isFlip?2:1); ++a){
for(int b=0; b<4; ++b){
Func::rotate(v2);
Func::normalize(v2);
minV = min(minV, v2);
}
Func::flip(v2);
}
s.insert(minV);
}
}
p.clear();
for(const auto& v : s){
set<vector<pair<int, int> > > t;
auto v2 = v;
for(int a=0; a<(isFlip?2:1); ++a){
for(int b=0; b<4; ++b){
Func::rotate(v2);
Func::normalize(v2);
t.insert(v2);
}
Func::flip(v2);
}
p.push_back(vector<vector<pair<int, int> > >(t.begin(), t.end()));
}
}
void makePolyomino(int n, vector<vector<pair<int, int> > >& p)
{
vector<vector<vector<pair<int, int> > > > p2;
makePolyomino(n, p2);
p.clear();
for(unsigned i=0; i<p2.size(); ++i){
for(unsigned j=0; j<p2[i].size(); ++j){
p.push_back(p2[i][j]);
}
}
}
int main()
{
int h, w, k;
cin >> h >> w >> k;
vector<vector<int> > grid(h, vector<int>(w));
for(int y=0; y<h; ++y){
for(int x=0; x<w; ++x){
char c;
cin >> c;
grid[y][x] = c - '0';
}
}
vector<vector<pair<int, int> > > p;
makePolyomino(k, p);
int n = p.size();
vector<tuple<int, int, int, int> > v;
for(int y=0; y<h; ++y){
for(int x=0; x<w; ++x){
for(int i=0; i<n; ++i){
int cnt = 1;
bool ok = true;
for(int j=0; j<k; ++j){
int y2 = y + p[i][j].first;
int x2 = x + p[i][j].second;
if(!(0 <= y2 && y2 < h && 0 <= x2 && x2 < w)){
ok = false;
break;
}
cnt *= grid[y2][x2];
}
if(!ok)
continue;
v.push_back(make_tuple(cnt, y, x, i));
}
}
}
sort(v.rbegin(), v.rend());
vector<tuple<int, int, int> > ans;
for(unsigned i=0; i<v.size(); ++i){
int cnt, y, x, index;
tie(cnt, y, x, index) = v[i];
bool ok = true;
for(int j=0; j<k; ++j){
int y2 = y + p[index][j].first;
int x2 = x + p[index][j].second;
if(grid[y2][x2] == -1){
ok = false;
break;
}
}
if(!ok)
continue;
ans.push_back(make_tuple(y, x, index));
for(int j=0; j<k; ++j){
int y2 = y + p[index][j].first;
int x2 = x + p[index][j].second;
grid[y2][x2] = -1;
}
}
cout << ans.size() << endl;
for(unsigned i=0; i<ans.size(); ++i){
int y, x, index;
tie(y, x, index) = ans[i];
for(int j=0; j<k; ++j){
int y2 = y + p[index][j].first + 1;
int x2 = x + p[index][j].second + 1;
cout << y2 << ' ' << x2 << endl;
}
}
return 0;
}
Submission Info
Submission Time |
|
Task |
A - Multiple Pieces |
User |
mamekin |
Language |
C++14 (GCC 5.4.1) |
Score |
945439 |
Code Size |
4990 Byte |
Status |
AC |
Exec Time |
1114 ms |
Memory |
133800 KB |
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 |
95634 / 1343058 |
89993 / 1343058 |
97481 / 1343058 |
90130 / 1343058 |
101847 / 1343058 |
91558 / 1343058 |
97943 / 1343058 |
87036 / 1343058 |
98219 / 1343058 |
95598 / 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 |
1050 ms |
133596 KB |
subtask_01_02.txt |
AC |
1114 ms |
133596 KB |
subtask_01_03.txt |
AC |
1073 ms |
132956 KB |
subtask_01_04.txt |
AC |
1074 ms |
133800 KB |
subtask_01_05.txt |
AC |
1103 ms |
132956 KB |
subtask_01_06.txt |
AC |
943 ms |
132828 KB |
subtask_01_07.txt |
AC |
1082 ms |
133596 KB |
subtask_01_08.txt |
AC |
916 ms |
132188 KB |
subtask_01_09.txt |
AC |
1091 ms |
133724 KB |
subtask_01_10.txt |
AC |
1010 ms |
132572 KB |