Submission #11354369


Source Code Expand

Copy
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author TM
 */


#include <bits/stdc++.h>
#include <utility>

#define MOD 1e9+7

using namespace std;

class a {
public:
  static void solve(std::istream &cin, std::ostream &cout) {
    vector<pair<int64_t, int64_t >> move{{0,  1},
                                         {0,  -1},
                                         {1,  0},
                                         {-1, 0}};
    vector<vector<int64_t>> g(30, vector<int64_t>(30));
    vector<vector<int64_t>> a_star(30, vector<int64_t>(30));
    vector<pair<int64_t, pair<int64_t, int64_t>>> gg;
    stack<pair<int64_t, int64_t>> s;
    vector<pair<int64_t, int64_t>> res;
    for (int i = 0; i < 30; ++i)
      for (int j = 0; j < 30; ++j) {
        cin >> g[i][j];
        gg.emplace_back(g[i][j], make_pair(i, j));
      }
    sort(gg.begin(), gg.end(), [](pair<int64_t, pair<int64_t, int64_t>> p, pair<int64_t, pair<int64_t, int64_t>> pp) {
      return p.first > pp.first;
    });

    for (int i = 0; i < 30; ++i)
      for (int j = 0; j < 30; ++j) {
        int cnt = 0;
        for (const auto &item : move) {
          int64_t next_x = i + item.first;
          int64_t next_y = j + item.second;
          if (next_x < 0 || next_x >= 30 || next_y < 0 || next_y >= 30)continue;
          if (g[i][j] == 0) continue;
          if (g[i][j] != g[next_x][next_y]) continue;
          cnt++;
        }
        a_star[i][j] = cnt;
      }
    for (const auto &data : gg) {
      int64_t i = data.second.first;
      int64_t j = data.second.second;
      if (g[i][j] == 0) continue;
      s.push(make_pair(i, j));
      while (!s.empty()) {
        auto p = s.top();
        s.pop();
        int64_t x = p.first;
        int64_t y = p.second;
        if (g[i][j] == 0) continue;
        g[x][y]--;
        res.emplace_back(x, y);
        vector<pair<int64_t, pair<int64_t, int64_t>>> tmp;
        for (const auto &item : move) {
          int64_t next_x = x + item.first;
          int64_t next_y = y + item.second;
          if (next_x < 0 || next_x >= 30 || next_y < 0 || next_y >= 30)continue;
          if (g[x][y] == 0) continue;
          if (g[x][y] != g[next_x][next_y]) continue;
          tmp.emplace_back(a_star[next_x][next_y], make_pair(next_x, next_y));
        }
        sort(tmp.begin(), tmp.end(), [](pair<int64_t, pair<int64_t, int64_t>> p, pair<int64_t, pair<int64_t, int64_t>> pp) {
          return p.first < pp.first;
        });
        for (const auto &data : tmp) {
          s.push(make_pair(data.second.first, data.second.second));
        }
        if (s.empty() && g[i][j] != 0) {
          s.push(make_pair(i, j));
        }
      }
    }
    for (const auto &item : res) {
      cout << item.first + 1 << " " << item.second + 1 << endl;
    }
  }
};


int main() {
  a solver;
  std::istream &in(std::cin);
  std::ostream &out(std::cout);
  solver.solve(in, out);
  return 0;
}

Submission Info

Submission Time
Task A - 高橋君の山崩しゲーム
User T_M
Language C++14 (GCC 5.4.1)
Score 743497
Code Size 3058 Byte
Status
Exec Time 82 ms
Memory 1420 KB

Test Cases

Set Name Score / Max Score Test Cases
test_01 74736 / 100000 subtask_01_01.txt
test_02 73675 / 100000 subtask_01_02.txt
test_03 74984 / 100000 subtask_01_03.txt
test_04 73638 / 100000 subtask_01_04.txt
test_05 74274 / 100000 subtask_01_05.txt
test_06 74397 / 100000 subtask_01_06.txt
test_07 74553 / 100000 subtask_01_07.txt
test_08 75096 / 100000 subtask_01_08.txt
test_09 73745 / 100000 subtask_01_09.txt
test_10 74399 / 100000 subtask_01_10.txt
Case Name Status Exec Time Memory
subtask_01_01.txt 76 ms 1420 KB
subtask_01_02.txt 77 ms 1420 KB
subtask_01_03.txt 78 ms 1420 KB
subtask_01_04.txt 82 ms 1420 KB
subtask_01_05.txt 78 ms 1420 KB
subtask_01_06.txt 75 ms 1420 KB
subtask_01_07.txt 77 ms 1420 KB
subtask_01_08.txt 76 ms 1420 KB
subtask_01_09.txt 78 ms 1420 KB
subtask_01_10.txt 79 ms 1420 KB