Submission #8242968
Source Code Expand
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <stack>
#include <complex>
#include <stdlib.h>
#include <stdio.h>
#include <functional>
#include <cfloat>
#include <math.h>
#include <numeric>
#include <string.h>
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<int, P> T;
P operator + (const P & l,const P & r){
return {l.fs + r.fs, l.sc + r.sc};
}
class Board{
public:
int a[32][32], h, w;
P v[4] = {P(0, 1), P(1, 0), P(0, -1), P(-1, 0)};
vector<T> sorted;
bool state[32][32];
int check[32][32];
Board(int hh, int ww){
h = hh; w = ww;
for(int i = 0; i < 32; i++){
for(int j = 0; j < 32; j++){
a[i][j] = 0;
}
}
for(int i = 0; i < 32; i++){
for(int j = 0; j < 32; j++){
check[i][j] = 0;
}
}
}
void prepare(){
for(int i = 1; i <= h; i++){
for(int j = 1; j <= w; j++){
sorted.emplace_back(T(a[i][j], P(i, j)));
}
}
sort(sorted.begin(), sorted.end());
reverse(sorted.begin(), sorted.end());
}
void init(){
for(int i = 0; i < 32; i++){
for(int j = 0; j < 32; j++){
state[i][j] = false;
}
}
}
int getValue(P c){
return a[c.fs][c.sc];
}
bool changeState(P x){
state[x.fs][x.sc] = true;
}
bool reached(P x){
return state[x.fs][x.sc];
}
P select(P c){
P ret = P(-1, -1);
int ma = 0;
for(auto dir: v){
P next = c + dir;
if(!reached(next) && getValue(next) > ma && getValue(next) < getValue(c)){
ret = next;
ma = getValue(next);
}
}
return ret;
}
vector<vector<P>> explore(){
int index = 0, su = 0;
vector<vector<P>> res;
vector<P> firstPath; firstPath.push_back(sorted[0].sc);
index++; su++;
res.push_back(firstPath);
changeState(sorted[0].sc);
while(true) {
// cout << su << endl;
if(su == h * w){
break;
}
int maxValue = 0;
for (int i = 0; i < res.size(); i++) {
// 探索はすでに終了
auto itr = --(res[i].end());
if((*itr).fs == -1){
continue;
}
P next = select(*itr);
if (next.fs == -1 && next.sc == -1) {
// 探索終了
res[i].emplace_back(P(-1, -1));
continue;
}
res[i].emplace_back(next); su++;
changeState(next);
maxValue = max(maxValue, getValue(next));
}
// 新たなパスが必要ならば追加
while (true) {
if (index == h * w) {
break;
}
if (reached(sorted[index].sc)) {
index++;
continue;
}
if (maxValue <= sorted[index].fs) {
vector<P> nextPath;
nextPath.push_back(sorted[index].sc); su++;
changeState(sorted[index].sc);
res.emplace_back(nextPath);
index++;
}
break;
}
}
return res;
}
void solve(){
init();
vector<vector<P>> exploreResult = explore();
outputResult(exploreResult);
checkResult();
}
int calcScore(vector<vector<int> > v){
int res = 0;
for(auto w: v){
res += *w.begin();
}
return res;
}
void output(P x){
check[x.fs][x.sc]++;
if(x.fs != -1 && x.sc != -1) {
cout << x.fs << " " << x.sc << endl;
}
}
void outputResult(vector<vector<P>> res){
for(auto w: res){
vector<int> valueList;
for(auto c: w){
valueList.push_back(getValue(c));
}
while(true){
if(valueList[0] == 0){
break;
}
valueList[0]--; output(w[0]);
for(int i = 1; i < valueList.size(); i++){
if(valueList[i] == 0){
break;
}
if(valueList[i] == valueList[i-1]){
valueList[i]--;
output(w[i]);
}
}
}
}
}
void checkResult(){
for(int i = 1; i <= h; i++){
for(int j = 1; j <= w; j++){
if(check[i][j] != a[i][j]){
cout << "check " << i << " " << j << endl;
}
}
}
}
};
int main(){
int h = 30, w = 30;
Board board = Board(h, w);
for(int i = 1; i <= h; i++){
for(int j = 1; j <= w; j++){
cin >> board.a[i][j];
}
}
board.prepare();
board.solve();
return 0;
}
Submission Info
Submission Time |
|
Task |
A - 高橋君の山崩しゲーム |
User |
bomac1 |
Language |
C++14 (GCC 5.4.1) |
Score |
785332 |
Code Size |
5641 Byte |
Status |
AC |
Exec Time |
81 ms |
Memory |
512 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 |
78650 / 100000 |
77855 / 100000 |
78683 / 100000 |
77920 / 100000 |
78164 / 100000 |
78807 / 100000 |
78833 / 100000 |
79020 / 100000 |
78782 / 100000 |
78618 / 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 |
73 ms |
512 KB |
subtask_01_02.txt |
AC |
79 ms |
512 KB |
subtask_01_03.txt |
AC |
76 ms |
512 KB |
subtask_01_04.txt |
AC |
81 ms |
512 KB |
subtask_01_05.txt |
AC |
77 ms |
512 KB |
subtask_01_06.txt |
AC |
80 ms |
512 KB |
subtask_01_07.txt |
AC |
80 ms |
512 KB |
subtask_01_08.txt |
AC |
75 ms |
512 KB |
subtask_01_09.txt |
AC |
80 ms |
512 KB |
subtask_01_10.txt |
AC |
81 ms |
512 KB |