Submission #1139698
Source Code Expand
#include <iostream> #include <vector> #include <random> #include <list> 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(P p) { return (p.first < N) && (0 <= p.first) && (p.second < N) && (0 <= p.second);; } 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 print_pos(P p) { cout << p.first+1 << " " << p.second+1 << "\n"; } void minus_path(list<P> &lp) { for(auto itr = lp.begin(); itr != lp.end(); ++itr) { P p = *itr; print_pos(p); A[p.first][p.second]--; } } list<P> get_path(P p) { int i = p.first; int j = p.second; if( A[i][j] == 0 ) { list<P> empty; return empty; } list<P> ret; ret.push_back( p ); vector< P > next_cand; vector< P > next_same; for(int k = 0; k < 4; k++) { int ni = i + di[k]; int nj = j + dj[k]; P np = P(ni, nj); if( in_bound(np) ) { if( A[ni][nj] == A[i][j]-1 ) next_cand.push_back( np ); else if (A[ni][nj] == A[i][j]) next_same.push_back( np ); } } if( next_cand.size() != 0 ) { P np = next_cand[ rnd() % next_cand.size() ]; list<P> ap = get_path( np ); ret.splice(ret.end(), ap); } // else if( next_same.size() != 0 ) { // P np = next_same[ rnd() % next_cand.size() ]; // list<P> ap = get_path( np ); // ap.splice(ap.end(), ret); // ret = ap; // } return ret; } 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]; } } while(true) { P mxp = get_max_index(); if( A[mxp.first][mxp.second] == 0) { break; } list<P> lp = get_path( mxp ); minus_path(lp); } // print_A(); return 0; }
Submission Info
Submission Time | |
---|---|
Task | A - 高橋君の山崩しゲーム |
User | sadtomato |
Language | C++14 (Clang 3.8.0) |
Score | 811064 |
Code Size | 2715 Byte |
Status | AC |
Exec Time | 2732 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 | 81596 / 100000 | 81085 / 100000 | 81432 / 100000 | 80472 / 100000 | 81059 / 100000 | 81058 / 100000 | 81358 / 100000 | 81122 / 100000 | 80912 / 100000 | 80970 / 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 | 2494 ms | 512 KB |
subtask_01_02.txt | AC | 2579 ms | 512 KB |
subtask_01_03.txt | AC | 2516 ms | 512 KB |
subtask_01_04.txt | AC | 2732 ms | 512 KB |
subtask_01_05.txt | AC | 2617 ms | 512 KB |
subtask_01_06.txt | AC | 2595 ms | 512 KB |
subtask_01_07.txt | AC | 2566 ms | 512 KB |
subtask_01_08.txt | AC | 2618 ms | 512 KB |
subtask_01_09.txt | AC | 2679 ms | 512 KB |
subtask_01_10.txt | AC | 2662 ms | 512 KB |