Submission #4927302
Source Code Expand
#include<iostream>
#include<vector>
#include<queue>
//https://rco-contest-2017-qual.contest.atcoder.jp/tasks/rco_contest_2017_qual_a
using namespace std;
#define FOR(i,a) for(int i=0;i<a;i++)
#define DEBUG
typedef vector<int> piece;
typedef vector<vector<int> > ans;
typedef pair<int, int> P;
//(n-1)*2,(n-1)*2+1->x,y
int news[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int board[52][52]={{}};
void input(){
int pip;cin>>pip;cin>>pip;cin>>pip;
char hoge;
FOR(i,50){
FOR(j,50){
cin>>hoge;
board[i+1][j+1]=hoge-'0';
}
}
}
void debprint(ans in){
for(auto &hoge:in){
for(auto &piyo:hoge){
cout<<piyo<<" ";
}
cout<<endl;
}
cout<<endl;
}
void pieceprint(ans in){
int hogehoge[52][52];
FOR(i,52){
FOR(j,52){
hogehoge[i][j]=0;
}
}
for(auto &hoge:in){
FOR(kk,8){
hogehoge[hoge[2*kk]][hoge[2*kk+1]]++;
}
}
FOR(i,52){
FOR(j,52){
cout<<hogehoge[i][j];
}
cout<<endl;
}
}
void ansprint(ans in){
int hogehoge[52][52];
for(auto &hoge:in){
FOR(kk,8){
cout<<hoge[2*kk]<<" "<<hoge[2*kk+1]<<endl;
}
}
}
long long int score(ans hoge){
long long int anss=0;
for(auto $tei:hoge){
long long int seki=1;
FOR(i,8){
seki=seki*board[2*i][2*i+1];
}
anss+=seki;
}
return anss;
}
ans make_easy_ans(){
int used[52][52];
FOR(j,52){
FOR(k,52){
used[j][k]=0;
}
}
int piecenum=0;
ans easyans;
for(int i=9;i>=1;i--){
FOR(j,52){
FOR(k,52){
if(board[j][k]==i and used[j][k]==0){
piece hoge;
hoge.push_back(j);
hoge.push_back(k);
int use[52][52];
FOR(c,52){
FOR(d,52){
if(used[c][d]==0){use[c][d]=0;}
else {use[c][d]=1;}
}
}
use[j][k]=1;
used[j][k]=1;
queue<P> near;
FOR(c,4){
if(use[j+news[c][0]][k+news[c][1]]==0){
near.push(P(j+news[c][0],k+news[c][1]));
use[j+news[c][0]][k+news[c][1]]=1;
}
}
int count=1;
while(count<8){
if(near.size()==0){
break;
}
int maxx=-1;
P maxxx=P(0,0);
FOR(p,near.size()){
P y=near.front();
near.pop();
if(board[y.first][y.second]>maxx){
near.push(maxxx);
maxxx=y;
maxx=board[y.first][y.second];
}
else{near.push(y);}
}
if(maxx<=0){
break;
}
else{
used[maxxx.first][maxxx.second]=1;
hoge.push_back(maxxx.first);
hoge.push_back(maxxx.second);
count++;
FOR(c,4){
if(use[maxxx.first+news[c][0]][maxxx.second+news[c][1]]==0){
near.push(P(maxxx.first+news[c][0],maxxx.second+news[c][1]));
use[maxxx.first+news[c][0]][maxxx.second+news[c][1]]=1;
}
}
}
if(count==8){
easyans.push_back(hoge);
piecenum++;
}
}
}
}
}
}
cout<<piecenum<<endl;
//debprint(easyans);
//pieceprint(easyans);
return easyans;
}
ans make_better_ans(int pieceupbond){
int used[52][52];
FOR(j,52){
FOR(k,52){
used[j][k]=0;
}
}
int piecenum=0;
ans betterans;
for(int i=9;i>=1;i--){
FOR(j,52){
FOR(k,52){
if(board[j][k]==i and used[j][k]==0){
piece hoge;
hoge.push_back(j);
hoge.push_back(k);
int use[52][52];
FOR(c,52){
FOR(d,52){
if(used[c][d]==0){use[c][d]=0;}
else {use[c][d]=1;}
}
}
use[j][k]=1;
used[j][k]=1;
queue<P> near;
FOR(c,4){
if(use[j+news[c][0]][k+news[c][1]]==0){
near.push(P(j+news[c][0],k+news[c][1]));
use[j+news[c][0]][k+news[c][1]]=1;
}
}
int count=1;
if(i>=9){
while(count<8){
if(near.size()==0){
break;
}
int maxx=-1;
FOR(p,near.size()){
P y=near.front();
near.pop();
if(board[y.first][y.second]>maxx){
maxx=board[y.first][y.second];
}
near.push(y);
}
if(maxx<=0){
break;
}
else{
int nextmax=-1;
P maxxx=P(0,0);
int maxkakomi=-1;
bool kakomi=false;
FOR(p,near.size()){
P y=near.front();
near.pop();
if(board[y.first][y.second]!=maxx){
near.push(y);
}
else{
int kakomico=0;
int nearmax=-1;
FOR(c,4){
if(used[y.first+news[c][0]][y.second+news[c][1]]==1){
kakomico++;
}
else if(board[y.first+news[c][0]][y.second+news[c][1]]>nearmax){
nearmax=board[y.first+news[c][0]][y.second+news[c][1]];
}
}
if(kakomi==true){}
else if(kakomico==4){
kakomi=true;
near.push(maxxx);
maxxx=y;
nextmax=nearmax;
}
else{
if(nextmax<=nearmax){
near.push(maxxx);
maxxx=y;
nextmax=nearmax;
}
}
}
}
used[maxxx.first][maxxx.second]=1;
hoge.push_back(maxxx.first);
hoge.push_back(maxxx.second);
count++;
FOR(c,4){
if(use[maxxx.first+news[c][0]][maxxx.second+news[c][1]]==0){
near.push(P(maxxx.first+news[c][0],maxxx.second+news[c][1]));
use[maxxx.first+news[c][0]][maxxx.second+news[c][1]]=1;
}
}
}
if(count==8){
betterans.push_back(hoge);
piecenum++;
}
}
}
else{
while(count<8){
if(near.size()==0){
break;
}
int maxx=-1;
P maxxx=P(0,0);
FOR(p,near.size()){
P y=near.front();
near.pop();
if(board[y.first][y.second]>maxx){
near.push(maxxx);
maxxx=y;
maxx=board[y.first][y.second];
}
else{near.push(y);}
}
if(maxx<=0){
break;
}
else{
used[maxxx.first][maxxx.second]=1;
hoge.push_back(maxxx.first);
hoge.push_back(maxxx.second);
count++;
FOR(c,4){
if(use[maxxx.first+news[c][0]][maxxx.second+news[c][1]]==0){
near.push(P(maxxx.first+news[c][0],maxxx.second+news[c][1]));
use[maxxx.first+news[c][0]][maxxx.second+news[c][1]]=1;
}
}
}
if(count==8){
betterans.push_back(hoge);
piecenum++;
}
}
}
}
}
}
}
cout<<piecenum<<endl;
//debprint(easyans);
//pieceprint(easyans);
return betterans;
}
int main(){
input();
ans k[10];
k[0]=make_better_ans(0);
ansprint(k[0]);
return 0;
}
Submission Info
Submission Time |
|
Task |
A - Multiple Pieces |
User |
atFFFofK |
Language |
C++14 (GCC 5.4.1) |
Score |
772729 |
Code Size |
8605 Byte |
Status |
AC |
Exec Time |
7 ms |
Memory |
384 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 |
77477 / 1343058 |
70053 / 1343058 |
78740 / 1343058 |
71176 / 1343058 |
86004 / 1343058 |
76342 / 1343058 |
82664 / 1343058 |
69292 / 1343058 |
81087 / 1343058 |
79894 / 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 |
7 ms |
384 KB |
subtask_01_02.txt |
AC |
7 ms |
384 KB |
subtask_01_03.txt |
AC |
7 ms |
384 KB |
subtask_01_04.txt |
AC |
7 ms |
384 KB |
subtask_01_05.txt |
AC |
7 ms |
384 KB |
subtask_01_06.txt |
AC |
7 ms |
384 KB |
subtask_01_07.txt |
AC |
7 ms |
384 KB |
subtask_01_08.txt |
AC |
7 ms |
384 KB |
subtask_01_09.txt |
AC |
7 ms |
384 KB |
subtask_01_10.txt |
AC |
7 ms |
384 KB |