Submission #1602920


Source Code Expand

//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

#define MAIN

const int h = 30, w = 30;
int board[30][30];
bool used[30][30];

vector<PII> func(int sx, int sy) {
  if(board[sy][sx] == 0) return {};
  vector<PII> v;
  v.PB({sy, sx});

  memset(used, false, sizeof(used));
  used[sy][sx] = true;

  int len = board[sy][sx];
  int x = sx, y = sy;
  REP(_, len) {
    int tmp = 0, idx = -1;
    REP(i, 4) {
      if(IN(0, w, x+dx[i]) && IN(0, h, y+dy[i])
        && !used[y+dy[i]][x+dx[i]] && tmp < board[y+dy[i]][x+dx[i]]) {
        tmp = board[y+dy[i]][x+dx[i]], idx = i;
      }
    }
    if(idx == -1) break;
    x = x+dx[idx], y = y+dy[idx];
    // cout << y << " " << x << " " << board[y][x] << endl;
    used[y][x] = true;
    chmin(len, (int)v.size()+board[y][x]-1);
    v.PB({y, x});
  }
  return v;
}

VI vv;
signed main(void)
{
  REP(i, h) REP(j, w) cin >> board[i][j];

  vector<PII> ans;
  int score = 0;

  int cnt = 0;
  int size = 0, times = 0;
  bool update = true;
  while(update) {
    if(cnt > 5) {
      int ma = 0, sx, sy;
      REP(i, h) REP(j, w) {
        if(board[i][j] > ma) ma = board[i][j], sx = j, sy = i;
      }
      if(!ma) break;

      vector<PII> v;
      v.PB({sy, sx});
      int x = sx, y = sy;
      int len = board[sy][sx];

      memset(used, false, sizeof(used));
      used[sy][sx] = true;

      REP(_, len) {
        int tmp = 0, idx = -1;
        REP(i, 4) {
          if(IN(0, w, x+dx[i]) && IN(0, h, y+dy[i]) && !used[y+dy[i]][x+dx[i]] && tmp < board[y+dy[i]][x+dx[i]]) {
            tmp = board[y+dy[i]][x+dx[i]], idx = i;
          }
        }
        if(idx == -1) break;
        x = x+dx[idx], y = y+dy[idx];
        // cout << y << " " << x << " " << board[y][x] << endl;
        used[y][x] = true;
        chmin(len, (int)v.size()+board[y][x]-1);
        v.PB({y, x});
      }
      // cout << "a" << endl;
      // for(auto i: v) cout << i.first << " "<< i.second << endl;

      size += v.size(); times++;
      vv.PB(v.size());

      // vを追っていって連続列をつくる
      FOR(i, 1, v.size()) {
        while(board[v[i].first][v[i].second] > board[v[i-1].first][v[i-1].second]-1) {
          board[v[i].first][v[i].second]--;
          ans.PB({v[i].first, v[i].second});
          score++;
        }
      }

      if(v.size() == 1) {
        while(board[v[0].first][v[0].second]) {
          board[v[0].first][v[0].second]--;
          ans.PB({v[0].first, v[0].second});
          score++;
        }
        continue;
      }
      bool endf = false;
      while(1) {
        // (sy, sx)からはじめて条件を満たすところまで1手番で操作する
        int len = 0;
        REP(i, v.size()-1) {
          board[v[i].first][v[i].second]--;
          ans.PB({v[i].first, v[i].second});
          if(board[v[i+1].first][v[i+1].second] == 0
            || board[v[i].first][v[i].second] != board[v[i+1].first][v[i+1].second]) {
            len = i;
            break;
          }
        }
        if(len == 0 && v.size() >= 2
          && board[v[v.size()-2].first][v[v.size()-2].second]
            == board[v[v.size()-1].first][v[v.size()-1].second]
          && board[v[v.size()-1].first][v[v.size()-1].second]) {
          board[v[v.size()-1].first][v[v.size()-1].second]--;
          ans.PB({v[v.size()-1].first, v[v.size()-1].second});
          len = v.size()-1;
        }
        if(endf && len == 0) break;
        if(len != 0) endf = true;
        score++;
      }
      // cout << "----------------------" << endl;
      // REP(i, h) {
      //   REP(j, w) {
      //     cout << board[i][j] << " ";
      //   }
      //   cout << endl;
      // }
      continue;
    }

    // 長さが大きいものを優先的に選ぶ
    // 最初の方に使う
    int ma = 0;
    REP(i, h) REP(j, w) chmax(ma, board[i][j]);
    if(!ma) break;

    vector<PII> v;
    REP(i, h) REP(j, w) {
      vector<PII> tmp = func(j, i);
      if(v.size() < tmp.size()) v = tmp;
    }
    times++, size += v.size();
    vv.PB(v.size());

    // cout << "a" << endl;
    // for(auto i: v) cout << i.first << "," << i.second << " "; cout << endl;

    // vを追っていって連続列をつくる
    FOR(i, 1, v.size()) {
      while(board[v[i].first][v[i].second] > 0
        && board[v[i].first][v[i].second] > board[v[i-1].first][v[i-1].second]-1) {
        board[v[i].first][v[i].second]--;
        ans.PB({v[i].first, v[i].second});
        score++;
      }
    }
    for(int i=v.size()-1; i>=0; --i) {
      if(board[v[i].first][v[i].second] == 0) v.pop_back();
      else break;
    }

    if(v.size() == 1) {
      while(board[v[0].first][v[0].second]) {
        board[v[0].first][v[0].second]--;
        ans.PB({v[0].first, v[0].second});
        score++;
      }
      continue;
    }
    bool endf = false;
    while(1) {
      // (sy, sx)からはじめて条件を満たすところまで1手番で操作する
      int len = 0;
      REP(i, v.size()-1) {
        board[v[i].first][v[i].second]--;
        ans.PB({v[i].first, v[i].second});
        if(board[v[i+1].first][v[i+1].second] == 0
          || board[v[i].first][v[i].second] != board[v[i+1].first][v[i+1].second]) {
          len = i;
          break;
        }
      }
      if(len == 0 && v.size() >= 2
        && board[v[v.size()-2].first][v[v.size()-2].second]
          == board[v[v.size()-1].first][v[v.size()-1].second]
        && board[v[v.size()-1].first][v[v.size()-1].second]) {
        //v.size()-1にも操作できる
        board[v[v.size()-1].first][v[v.size()-1].second]--;
        ans.PB({v[v.size()-1].first, v[v.size()-1].second});
        len = v.size()-1;
      }
      if(endf && len == 0) break;
      if(len != 0) endf = true;
      score++;
    }
    cnt++;
    // cout << "----------------------" << endl;
    // REP(i, h) {
    //   REP(j, w) {
    //     cout << board[i][j] << " ";
    //   }
    //   cout << endl;
    // }
  }

  // cout << "end" << endl;
  REP(i, h) {
    REP(j, w) {
      while(board[i][j]) board[i][j]--, ans.PB({i, j}), score++;
    }
  }


#ifdef MAIN
  for(PII i: ans) cout << i.first+1 << " " << i.second+1 << endl;
#else
  for(int i: vv) cout << i << " "; cout << endl;
  cout << "score:" << 100000 - score << " " << ans.size() << endl;
  cout << size << " " << times << " " << size/times << endl;
#endif

  return 0;
}

Submission Info

Submission Time
Task A - 高橋君の山崩しゲーム
User ferin_tech
Language C++14 (GCC 5.4.1)
Score 729763
Code Size 7321 Byte
Status AC
Exec Time 84 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 74475 / 100000 71978 / 100000 74138 / 100000 71824 / 100000 72762 / 100000 74248 / 100000 73001 / 100000 72748 / 100000 72522 / 100000 72067 / 100000
Status
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
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 76 ms 1016 KB
subtask_01_02.txt AC 81 ms 1016 KB
subtask_01_03.txt AC 80 ms 1016 KB
subtask_01_04.txt AC 84 ms 1016 KB
subtask_01_05.txt AC 78 ms 1016 KB
subtask_01_06.txt AC 80 ms 1016 KB
subtask_01_07.txt AC 80 ms 1016 KB
subtask_01_08.txt AC 77 ms 1016 KB
subtask_01_09.txt AC 81 ms 1016 KB
subtask_01_10.txt AC 80 ms 1016 KB