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
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 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