Submission #1138909
Source Code Expand
#include <iostream>
#include <vector>
#include <random>
using namespace std;
// template for creating 2d vector
template<typename T>
vector<vector<T>> make_2d_vector(size_t rows, size_t cols, T init)
{ return vector< vector<T> >(rows, vector<T>(cols, init)); }
typedef vector< vector<int> > two_d_vector;
random_device rnd;
#define debug(x) cout << #x << "==" << x << endl;
const int inf = 100000000;
typedef long long ll;
#define N 30
auto A = make_2d_vector(30, 30, 0);
//移動4方向のベクトル
int di[4] = {1, 0, -1, 0};
int dj[4] = {0, 1, 0, -1};
typedef pair<int,int> P;
bool in_bound(int i) {
return (i < N) && (0 <= i);
}
void print_A() {
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
cout << A[i][j] << " ";
} cout << "\n";
} cout << "\n";
}
void put(int i, int j) {
if( A[i][j] == 0 ) {
return;
}
A[i][j] -= 1;
cout << i+1 << " " << j+1 << "\n";
int num = A[i][j];
vector< P > next_cand;
for(int k = 0; k < 4; k++) {
int ni = i + di[k]; int nj = j + dj[k];
if( in_bound(ni) && in_bound(nj) ) {
if( A[ni][nj] == num ) next_cand.push_back( P(ni, nj) );
}
}
if( next_cand.size() != 0 ) {
// P p = next_cand[ 0 ];
P p = next_cand[ rnd() % next_cand.size() ];
put(p.first, p.second );
}
}
P get_max_index() {
P max_index;
int max_n = 0;
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
int n = A[i][j];
if(max_n < n) {
max_index = P(i,j);
max_n = n;
} else if (max_n == n) {
if( rnd() % 2 == 0 ) max_index = P(i,j);
}
}
}
return max_index;
}
int main() {
ios::sync_with_stdio(false);
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
cin >> A[i][j];
}
}
// for(int i = 0; i < N; i++) {
// for(int j = 0; j < N; j++) {
// int n = A[i][j];
// for(int k = 0; k < n; k++ ) {
// put(i, j);
// }
// }
// }
while(true) {
P mxi = get_max_index();
int i = mxi.first; int j = mxi.second;
if( A[i][j] == 0) { break; }
put(i, j);
}
// for(int i = 0; i < N; i++) {
// for(int j = 0; j < N; j++) {
// two_d_vector B = A;
// debug(i);
// debug(j);
// debug(put_sim(i, j, 0, 3, B));
// }
// }
// print_A();
return 0;
}
Submission Info
Submission Time |
|
Task |
A - 高橋君の山崩しゲーム |
User |
sadtomato |
Language |
C++14 (Clang 3.8.0) |
Score |
810441 |
Code Size |
2457 Byte |
Status |
AC |
Exec Time |
2688 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 |
81177 / 100000 |
81180 / 100000 |
81240 / 100000 |
80578 / 100000 |
80974 / 100000 |
81129 / 100000 |
81284 / 100000 |
80965 / 100000 |
80999 / 100000 |
80915 / 100000 |
Status |
|
|
|
|
|
|
|
|
|
|
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 |
2601 ms |
512 KB |
subtask_01_02.txt |
AC |
2528 ms |
512 KB |
subtask_01_03.txt |
AC |
2549 ms |
512 KB |
subtask_01_04.txt |
AC |
2688 ms |
512 KB |
subtask_01_05.txt |
AC |
2619 ms |
512 KB |
subtask_01_06.txt |
AC |
2562 ms |
512 KB |
subtask_01_07.txt |
AC |
2572 ms |
512 KB |
subtask_01_08.txt |
AC |
2659 ms |
512 KB |
subtask_01_09.txt |
AC |
2625 ms |
512 KB |
subtask_01_10.txt |
AC |
2646 ms |
512 KB |