Submission #1143737


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;

#ifdef _WIN32
#include <Windows.h>
#else
#include <sys/time.h>
#endif

class TicToc
{
private:
	double getCurrTime(){
	#ifdef MAMEKIN_PC
		return GetTickCount() * 1e-3;
	#else
		struct timeval tv;
		gettimeofday(&tv, NULL);
		return tv.tv_sec + tv.tv_usec * 1e-6;
	#endif
	}
	double startTime;
public:
	void tic(){
		startTime = getCurrTime();
	}
	double toc(){
		return getCurrTime() - startTime;
	}
};

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]);
		}
	}
}

unsigned xor128(){
    static unsigned x=12346789,y=362436069,z=521288629,w=88675123;
    unsigned t;
    t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
}

int main()
{
	TicToc tictoc;
	tictoc.tic();

	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, 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 || cnt == 0)
					continue;

				v.push_back(make_tuple(cnt, -1, y, x, i));
			}
		}
	}
	
	long long maxSum = 0;
	vector<tuple<int, int, int> > ans;
	do{
		for(unsigned i=0; i<v.size(); ++i)
			get<1>(v[i]) = xor128();
		sort(v.rbegin(), v.rend());

		long long sum = 0;
		vector<tuple<int, int, int> > ans2;
		vector<vector<bool> > check(h, vector<bool>(w, false));
		for(unsigned i=0; i<v.size(); ++i){
			int cnt, tmp, y, x, index;
			tie(cnt, tmp, 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(check[y2][x2]){
					ok = false;
					break;
				}
			}
			if(!ok)
				continue;
		
			sum += cnt;
			ans2.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;
				check[y2][x2] = true;
			}
		}

		if(maxSum < sum){
			maxSum = sum;
			ans = ans2;
		}
	}while(tictoc.toc() < 9.5);

	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 949735
Code Size 6016 Byte
Status AC
Exec Time 9742 ms
Memory 84736 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 95979 / 1343058 90231 / 1343058 97708 / 1343058 90383 / 1343058 102564 / 1343058 91861 / 1343058 98618 / 1343058 87548 / 1343058 99100 / 1343058 95743 / 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 9648 ms 84608 KB
subtask_01_02.txt AC 9740 ms 82816 KB
subtask_01_03.txt AC 9546 ms 83840 KB
subtask_01_04.txt AC 9551 ms 83456 KB
subtask_01_05.txt AC 9695 ms 83072 KB
subtask_01_06.txt AC 9561 ms 84736 KB
subtask_01_07.txt AC 9742 ms 84352 KB
subtask_01_08.txt AC 9526 ms 83840 KB
subtask_01_09.txt AC 9626 ms 83328 KB
subtask_01_10.txt AC 9606 ms 84096 KB