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