Chokudai Contest 001

Submission #9902416

Source codeソースコード

#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <utility>
#include <stack>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <climits>
#include <set>
#include <cmath>
#include <numeric>
#include <iomanip>
#include <random>
#include <chrono>

using namespace std;
const int N = 30;
int A[30][30];
int ans_size = 0;
int h_moves[4] = {-1, 0, 1, 0};
int w_moves[4] = {0, -1, 0, 1};
vector <pair<int, int> > ans;
chrono::system_clock::time_point start;
chrono::system_clock::time_point cur_time;
void input(){
  for(int i = 0; i < N; i++){
    for(int j = 0; j < N; j++){
      cin >> A[i][j];
    }
  }
}

bool is_top(int i, int j){
  if(A[i][j] == 0){
    return false;
  }
  for(int k = 0; k < 4; k++){
    if(0 <= i + h_moves[k] && i + h_moves[k] < N 
      && 0 <= j + w_moves[k] && j + w_moves[k] < N
      && A[i][j] < A[i + h_moves[k]][j + w_moves[k]]){
        return false;
    }
  }
  return true;
}

pair <int, int> find_top(){
  for(int i = 0; i < N; i++){
    for(int j = 0; j < N; j++){
      if(is_top(i, j)){
        return make_pair(i, j);
      }
    }
  }
  return make_pair(-1, -1);
}

void solve(){
  while(true){
    auto tmp = find_top();
    if(tmp.first < 0){
      return;
    }
    int i = tmp.first;
    int j = tmp.second;
    //cout << i << " " << j << endl;
    ans.push_back(make_pair(i + 1, j + 1));
    ans_size ++;
    A[i][j] --;
    int cur_i = i;
    int cur_j = j;
    while(true){
      //cout << cur_i << " " << cur_j << endl;
      bool changed = false;
      for(int k = 0; k < 4; k++){
        int next_i = cur_i + h_moves[k];
        int next_j = cur_j + w_moves[k];
        //cout << next_i << " " << next_j << endl;
        if(0 <= next_i && next_i < N && 0 <= next_j && next_j < N){
          if(A[cur_i][cur_j] == A[next_i][next_j] && A[next_i][next_j] != 0){
            ans.push_back(make_pair(next_i + 1, next_j + 1));
            ans_size ++;
            A[next_i][next_j] --;
            changed = true;
            cur_i = next_i;
            cur_j = next_j;
            break;
          }
        }
      }
      if(!changed){
        break;
      }
    }
  }
}

void output(){
  for(int i = 0; i < ans.size(); i++){
    cout << ans[i].first << " " << ans[i].second << endl;
  }
}

int main(void){
  start = chrono::system_clock::now();
  input();
  solve();
  output();
  return 0;
}

Submission

Task問題 A - 高橋君の山崩しゲーム
User nameユーザ名 katom
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 867504
Source lengthソースコード長 2504 Byte
File nameファイル名
Exec time実行時間 114 ms
Memory usageメモリ使用量 1016 KB

Test case

Set

Set name Score得点 / Max score Cases
test_01 86889 / 100000 subtask_01_01.txt
test_02 86834 / 100000 subtask_01_02.txt
test_03 86791 / 100000 subtask_01_03.txt
test_04 86347 / 100000 subtask_01_04.txt
test_05 86218 / 100000 subtask_01_05.txt
test_06 86434 / 100000 subtask_01_06.txt
test_07 87593 / 100000 subtask_01_07.txt
test_08 86482 / 100000 subtask_01_08.txt
test_09 86695 / 100000 subtask_01_09.txt
test_10 87221 / 100000 subtask_01_10.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
subtask_01_01.txt AC 103 ms 1016 KB
subtask_01_02.txt AC 109 ms 1016 KB
subtask_01_03.txt AC 109 ms 1016 KB
subtask_01_04.txt AC 114 ms 1016 KB
subtask_01_05.txt AC 108 ms 1016 KB
subtask_01_06.txt AC 110 ms 1016 KB
subtask_01_07.txt AC 107 ms 1016 KB
subtask_01_08.txt AC 105 ms 1016 KB
subtask_01_09.txt AC 110 ms 1016 KB
subtask_01_10.txt AC 109 ms 1016 KB