Submission #8237592


Source Code Expand

#include <bits/stdc++.h>
#define LLI long long int
#define FOR(v, a, b) for(LLI v = (a); v < (b); ++v)
#define FORE(v, a, b) for(LLI v = (a); v <= (b); ++v)
#define REP(v, n) FOR(v, 0, n)
#define REPE(v, n) FORE(v, 0, n)
#define REV(v, a, b) for(LLI v = (a); v >= (b); --v)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define ITR(it, c) for(auto it = (c).begin(); it != (c).end(); ++it)
#define RITR(it, c) for(auto it = (c).rbegin(); it != (c).rend(); ++it)
#define EXIST(c,x) ((c).find(x) != (c).end())
#define fst first
#define snd second
#define popcount __builtin_popcount
#define UNIQ(v) (v).erase(unique(ALL(v)), (v).end())
#define bit(i) (1LL<<(i))

#ifdef DEBUG
#include <misc/C++/Debug.cpp>
#else
#define dump(...) ((void)0)
#endif

#define gcd __gcd

using namespace std;
template <class T> constexpr T lcm(T m, T n){return m/gcd(m,n)*n;}

template <typename I> void join(ostream &ost, I s, I t, string d=" "){for(auto i=s; i!=t; ++i){if(i!=s)ost<<d; ost<<*i;}ost<<endl;}
template <typename T> istream& operator>>(istream &is, vector<T> &v){for(auto &a : v) is >> a; return is;}

template <typename T, typename U> bool chmin(T &a, const U &b){return (a>b ? a=b, true : false);}
template <typename T, typename U> bool chmax(T &a, const U &b){return (a<b ? a=b, true : false);}
template <typename T, size_t N, typename U> void fill_array(T (&a)[N], const U &v){fill((U*)a, (U*)(a+N), v);}

struct Init{
  Init(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(12);
    cerr << fixed << setprecision(12);
  }
}init;

struct XorShift{
  static uint64_t rand(){
    static uint64_t x = 1234567889, y = 362436069, z = 521288629, w = 88675123;

    uint64_t t = (x ^ (x << 11));
    x = y;
    y = z;
    z = w;
    w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
    return w;
  }

  static uint64_t rand(uint64_t s, uint64_t t){ // [s,t]
    return s + rand() % (t-s);
  }
};


template <typename F>
struct FixPoint : F{
  explicit constexpr FixPoint(F &&f) noexcept : F(forward<F>(f)){}

  template <typename... Args>
  constexpr decltype(auto) operator()(Args &&... args) const {
    return F::operator()(*this, forward<Args>(args)...);
  }
};

template <typename F>
static inline constexpr decltype(auto) make_fix_point(F &&f){
  return FixPoint<F>(forward<F>(f));
}


int dir[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}};



int main(){
  int N = 30;
  vector<vector<int>> A(N, vector<int>(N)); cin >> A;


  auto dfs =
    make_fix_point([&](auto &&dfs, int x, int y) -> void{
                     if(A[x][y] == 0) return;

                     A[x][y] -= 1;

                     cout << x+1 << " " << y+1 << endl;


                     REP(i,4){
                       int nx = x + dir[i][0], ny = y + dir[i][1];

                       if(nx >= 0 and nx < N and ny >= 0 and ny < N and A[nx][ny] == A[x][y]){
                         dfs(nx, ny);
                         break;
                       }
                     }
                   });

  

  int count = 0;
  
  while(1){
    bool contn = false;
    REP(i,N){
      REP(j,N){
        if(A[i][j] != 0){
          contn = true;
          break;
        }
      }
    }

    if(not contn) break;

    int x = 0;
    int y = 0;

    REP(i,N){
      REP(j,N){
        if(A[i][j] > A[x][y] and XorShift::rand() % 100 >= 5){
          x = i;
          y = j;
        }
      }
    }
    

    if(A[x][y] == 0) continue;
    
    dfs(x, y);

    count += 1;
    /*
    REP(i,N){
      join(cerr, ALL(A[i]));
      }*/
  }
  
  dump(count);
  

  


  return 0;
}

Submission Info

Submission Time
Task A - 高橋君の山崩しゲーム
User you070707
Language C++14 (GCC 5.4.1)
Score 798711
Code Size 3745 Byte
Status AC
Exec Time 102 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 79934 / 100000 79855 / 100000 80355 / 100000 78993 / 100000 79855 / 100000 79961 / 100000 80129 / 100000 79990 / 100000 79780 / 100000 79859 / 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 95 ms 512 KB
subtask_01_02.txt AC 97 ms 512 KB
subtask_01_03.txt AC 97 ms 512 KB
subtask_01_04.txt AC 102 ms 512 KB
subtask_01_05.txt AC 101 ms 512 KB
subtask_01_06.txt AC 95 ms 512 KB
subtask_01_07.txt AC 101 ms 512 KB
subtask_01_08.txt AC 95 ms 512 KB
subtask_01_09.txt AC 100 ms 512 KB
subtask_01_10.txt AC 101 ms 512 KB