Submission #8224867


Source Code Expand

#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())
#define ll long long
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;
//typedef vector<unsigned int>vec;
typedef vector<ll>vec;
typedef vector<vec> mat;
typedef vector<vector<int>> Graph;

//const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
//const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const int dh[4] = { 0, -1, 0, 1 };
const int dw[4] = { -1, 0, 1, 0 };

const int INF = 1000000000;
const ll LINF = 1000000000000000000;//1e18
const ll  MOD = 1000000007;
//const ll MOD = 998244353;
const double PI = acos(-1.0);
const double EPS = 1e-10;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline void add(T &a, T b){a = ((a+b) % MOD + MOD) % MOD;};

int ansScore;

int N = 30;
int cnt_zero = 0;
int inputMap[30][30];
vector<pair<int, int>> ans;
/*
typedef vector<string> Board;
typedef pair<int, Board> State;
typedef pair<int, State> elem;
*/
constexpr double TL = 9.90;

constexpr ll CYCLES_PER_SEC = 2800000000;
struct Timer {
  ll start;

  Timer() { reset(); }

  void reset() { start = getCycle(); }

  inline double get() { return (double) (getCycle() - start) / CYCLES_PER_SEC; }

  inline ll getCycle() {
    unsigned low, high;
    __asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));
    return ((ll) low) | ((ll) high << 32);
  }
};
Timer timer;

struct RandomNumberGenerator {
  mt19937 mt;

  RandomNumberGenerator() : mt(chrono::steady_clock::now().time_since_epoch().count()) {}

  int operator()(int a, int b) { // [a, b)
    uniform_int_distribution< int > dist(a, b - 1);
    return dist(mt);
  }

  int operator()(int b) { // [0, b)
    return (*this)(0, b);
  }
};

RandomNumberGenerator rm;

uint32_t XorShift(void) {
	static uint32_t x = 123456789;
	static uint32_t y = 362436069;
	static uint32_t z = 521288629;
	static uint32_t w = 88675123;
	uint32_t t;

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

double MetropolisHastings(int dif,double t){
    double ret=exp(dif/t);
    return ret;
}

double Prob(void){
	double ret = (double)XorShift() / UINT_MAX;
	return ret;
}

void input(){
    REP(i,N){
        REP(j,N){
            cin >> inputMap[i][j];
        }
    }
}

void output(){
    for(auto out : ans){
        cout << out.first + 1 << " " << out.second + 1 << endl;
    }
}

bool isTop(int H, int W){
    REP(i,4){
        int nh = H + dh[i], nw = W + dw[i];
        if(!(0 <= nh && nh < N && 0 <= nw && nw < N)) continue;
        if(inputMap[H][W] <= 0 || inputMap[nh][nw] > inputMap[H][W]) return false;
    }
    return true;
}

pair<int, int> chooseTop(){
    REP(i,N) REP(j,N){
        if(isTop(i, j)) return make_pair(i, j);
    }
    return make_pair(-1, -1);
}

void init(){
    timer.reset();
    //ansScore = ansCalc();
    //cout << ansScore << endl;
}

void solve(){
    //double start_temp = 110.0;
    //double end_temp = 10.0;
    //auto start_time = timer.get();
    //double C = TL * 100; //許容する確率定数
    //double next; //遷移するかしないかの許容ライン
    //int cnt = 0;
    auto p = chooseTop();
    while(p.first != -1 && p.second != -1){
        while(1){
            int H, W;
            tie(H, W) = p;
            cout << H + 1 << " " << W + 1 << endl;
            inputMap[H][W]--;
            pair<int, int> next;
            next.first = -1, next.second = -1;
            REP(i,4){
                int nh = H + dh[i], nw = W + dw[i];
                if(!(0 <= nh && nh < N && 0 <= nw && nw < N)) continue;
                if(inputMap[H][W] == inputMap[nh][nw] && inputMap[nh][nw] > 0){
                    next = make_pair(nh, nw);
                    break;
                }
            }
            if(next.first != -1 && next.second != -1){
                p = next;
                continue;
            }
            break;
        }
        p = chooseTop();
    }
    //cerr << "cnt : " << cnt << endl;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    input();
    init();
    solve();
    output();
}

Submission Info

Submission Time
Task A - 高橋君の山崩しゲーム
User Bondo416
Language C++14 (GCC 5.4.1)
Score 862195
Code Size 4546 Byte
Status AC
Exec Time 119 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 86606 / 100000 86095 / 100000 85835 / 100000 85704 / 100000 86356 / 100000 85874 / 100000 86706 / 100000 86275 / 100000 86209 / 100000 86535 / 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 106 ms 512 KB
subtask_01_02.txt AC 117 ms 512 KB
subtask_01_03.txt AC 113 ms 512 KB
subtask_01_04.txt AC 119 ms 512 KB
subtask_01_05.txt AC 110 ms 512 KB
subtask_01_06.txt AC 115 ms 512 KB
subtask_01_07.txt AC 113 ms 512 KB
subtask_01_08.txt AC 110 ms 512 KB
subtask_01_09.txt AC 113 ms 512 KB
subtask_01_10.txt AC 111 ms 512 KB