Submission #8242968


Source Code Expand

#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <stack>
#include <complex>
#include <stdlib.h>
#include <stdio.h>
#include <functional>
#include <cfloat>
#include <math.h>
#include <numeric>
#include <string.h>


#define fs first
#define sc second

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef pair<int, P> T;


P operator + (const P & l,const P & r){
    return {l.fs + r.fs, l.sc + r.sc};
}


class Board{
public:
    int a[32][32], h, w;
    P v[4] = {P(0, 1), P(1, 0), P(0, -1), P(-1, 0)};
    vector<T> sorted;
    bool state[32][32];
    int check[32][32];

    Board(int hh, int ww){
        h = hh; w = ww;
        for(int i = 0; i < 32; i++){
            for(int j = 0; j < 32; j++){
                a[i][j] = 0;
            }
        }
        for(int i = 0; i < 32; i++){
            for(int j = 0; j < 32; j++){
                check[i][j] = 0;
            }
        }
    }

    void prepare(){
        for(int i = 1; i <= h; i++){
            for(int j = 1; j <= w; j++){
                sorted.emplace_back(T(a[i][j], P(i, j)));
            }
        }
        sort(sorted.begin(), sorted.end());
        reverse(sorted.begin(), sorted.end());
    }

    void init(){
        for(int i = 0; i < 32; i++){
            for(int j = 0; j < 32; j++){
                state[i][j] = false;
            }
        }
    }

    int getValue(P c){
        return a[c.fs][c.sc];
    }

    bool changeState(P x){
        state[x.fs][x.sc] = true;
    }

    bool reached(P x){
        return state[x.fs][x.sc];
    }

    P select(P c){
        P ret = P(-1, -1);
        int ma = 0;
        for(auto dir: v){
            P next = c + dir;
            if(!reached(next) && getValue(next) > ma && getValue(next) < getValue(c)){
                ret = next;
                ma = getValue(next);
            }
        }
        return ret;
    }

    vector<vector<P>> explore(){
        int index = 0, su = 0;

        vector<vector<P>> res;
        vector<P> firstPath;  firstPath.push_back(sorted[0].sc);
        index++; su++;

        res.push_back(firstPath);
        changeState(sorted[0].sc);

        while(true) {
//            cout << su << endl;
            if(su == h * w){
                break;
            }

            int maxValue = 0;
            for (int i = 0; i < res.size(); i++) {
                // 探索はすでに終了
                auto itr = --(res[i].end());
                if((*itr).fs == -1){
                    continue;
                }

                P next = select(*itr);
                if (next.fs == -1 && next.sc == -1) {
                    // 探索終了
                    res[i].emplace_back(P(-1, -1));
                    continue;
                }

                res[i].emplace_back(next);   su++;
                changeState(next);
                maxValue = max(maxValue, getValue(next));
            }

            // 新たなパスが必要ならば追加
            while (true) {
                if (index == h * w) {
                    break;
                }
                if (reached(sorted[index].sc)) {
                    index++;
                    continue;
                }
                if (maxValue <= sorted[index].fs) {
                    vector<P> nextPath;
                    nextPath.push_back(sorted[index].sc);   su++;
                    changeState(sorted[index].sc);
                    res.emplace_back(nextPath);
                    index++;
                }
                break;
            }
        }

        return res;
    }

    void solve(){
        init();
        vector<vector<P>> exploreResult = explore();
        outputResult(exploreResult);

        checkResult();
    }

    int calcScore(vector<vector<int> > v){
        int res = 0;
        for(auto w: v){
            res += *w.begin();
        }
        return res;
    }

    void output(P x){
        check[x.fs][x.sc]++;
        if(x.fs != -1 && x.sc != -1) {
            cout << x.fs << " " << x.sc << endl;
        }
    }

    void outputResult(vector<vector<P>> res){
        for(auto w: res){
            vector<int> valueList;
            for(auto c: w){
                valueList.push_back(getValue(c));
            }
            while(true){
                if(valueList[0] == 0){
                    break;
                }
                valueList[0]--; output(w[0]);
                for(int i = 1; i < valueList.size(); i++){
                    if(valueList[i] == 0){
                        break;
                    }
                    if(valueList[i] == valueList[i-1]){
                        valueList[i]--;
                        output(w[i]);
                    }
                }
            }
        }
    }

    void checkResult(){
        for(int i = 1; i <= h; i++){
            for(int j = 1; j <= w; j++){
                if(check[i][j] != a[i][j]){
                    cout << "check " << i << " " << j << endl;
                }
            }
        }
    }
};


int main(){
    int h = 30, w = 30;
    Board board = Board(h, w);
    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            cin >> board.a[i][j];
        }
    }
    board.prepare();
    board.solve();


    return 0;
}

Submission Info

Submission Time
Task A - 高橋君の山崩しゲーム
User bomac1
Language C++14 (GCC 5.4.1)
Score 785332
Code Size 5641 Byte
Status AC
Exec Time 81 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 78650 / 100000 77855 / 100000 78683 / 100000 77920 / 100000 78164 / 100000 78807 / 100000 78833 / 100000 79020 / 100000 78782 / 100000 78618 / 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 73 ms 512 KB
subtask_01_02.txt AC 79 ms 512 KB
subtask_01_03.txt AC 76 ms 512 KB
subtask_01_04.txt AC 81 ms 512 KB
subtask_01_05.txt AC 77 ms 512 KB
subtask_01_06.txt AC 80 ms 512 KB
subtask_01_07.txt AC 80 ms 512 KB
subtask_01_08.txt AC 75 ms 512 KB
subtask_01_09.txt AC 80 ms 512 KB
subtask_01_10.txt AC 81 ms 512 KB