Submission #3563970
Source Code Expand
#include <iostream>
#include <cassert>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int,int> P;
int N = 30,A[31][31],count = 0,sum = 0;
int dx[4] = {-1,1,0,0},dy[4] = {0,0,-1,1},visited[31][31] = {{0}};
vector<P> ans;
void print(){
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
cout << A[i][j] << (j!=N? " ":"\n");
}
}
}
bool in(int x,int y){
return 1<=x && x<=N && 1<=y && y<=N;
}
void dec(){
priority_queue<P> Q;
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
Q.push({A[i][j],i*31+j});
}
}
while(!Q.empty()){
P p = Q.top(); Q.pop();
int i = p.second/31,j = p.second%31;
int ma = 0;
for(int k=0;k<4;k++){
int ni = i+dx[k],nj = j+dy[k];
if(!in(ni,nj)) continue;
ma = max(ma,A[ni][nj]);
}
while(ma+1<A[i][j]){
A[i][j]--;
ans.push_back({i,j});
count++;
}
}
}
void dec2(){
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
int ma = 0;
for(int k=0;k<4;k++){
int ni = i+dx[k],nj = j+dy[k];
if(!in(ni,nj) || A[i][j]-1!=A[ni][nj]) continue;
for(int l=0;l<4;l++){
int nni = ni+dx[l],nnj = nj+dy[l];
if(!in(nni,nnj) || (nni==i && nnj==j)) continue;
ma = max(ma,A[nni][nnj]);
}
while(ma+1<A[ni][nj]){
ans.push_back({i,j});
ans.push_back({ni,nj});
count += 2;
A[i][j]--; A[ni][nj]--;
}
break;
}
}
}
}
vector<P> longest(int x,int y,vector<P> v){
v.push_back({x,y});
vector<P> result = v;
if(A[x][y]==1) return result;
for(int k=0;k<4;k++){
int nx = x+dx[k],ny = y+dy[k];
if(!in(nx,ny)) continue;
if(A[x][y]-1==A[nx][ny]){
vector<P> u = longest(nx,ny,v);
if(result.size()<u.size()){
result = u;
}
}
}
return result;
}
int main(){
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
cin >> A[i][j];
sum += A[i][j];
}
}
dec(); dec2();
while(count<sum){
bool judge = false;
vector<P> res;
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
if(A[i][j]==0) continue;
vector<P> a;
vector<P> now = longest(i,j,a);
if(res.size()<now.size()){
res = now;
}
}
}
for(int i=0;i<res.size();i++){
ans.push_back({res[i].first,res[i].second});
A[res[i].first][res[i].second]--;
count++;
}
}
for(int i=0;i<ans.size();i++){
cout << ans[i].first << " " << ans[i].second << endl;
}
}
Submission Info
Submission Time |
|
Task |
A - 高橋君の山崩しゲーム |
User |
idsigma |
Language |
C++14 (GCC 5.4.1) |
Score |
801322 |
Code Size |
2410 Byte |
Status |
AC |
Exec Time |
780 ms |
Memory |
1016 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 |
80819 / 100000 |
79869 / 100000 |
80076 / 100000 |
80127 / 100000 |
79913 / 100000 |
80069 / 100000 |
80506 / 100000 |
80188 / 100000 |
80035 / 100000 |
79720 / 100000 |
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 |
702 ms |
1016 KB |
subtask_01_02.txt |
AC |
732 ms |
1012 KB |
subtask_01_03.txt |
AC |
772 ms |
1016 KB |
subtask_01_04.txt |
AC |
754 ms |
1012 KB |
subtask_01_05.txt |
AC |
778 ms |
1016 KB |
subtask_01_06.txt |
AC |
759 ms |
1012 KB |
subtask_01_07.txt |
AC |
738 ms |
1016 KB |
subtask_01_08.txt |
AC |
719 ms |
1016 KB |
subtask_01_09.txt |
AC |
724 ms |
1016 KB |
subtask_01_10.txt |
AC |
780 ms |
1016 KB |