Submission #1216795


Source Code Expand

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <random>

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define FST first
#define SND second
#define SZ(a) int((a).size())
#define EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())
#define SORT(c) sort((c).begin(), (c).end())

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

const int MOD = 1000000007;
const char ENDL = '\n';

#define dump(x) cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")"  << " " << __FILE__ << endl;

const int N = 30;

int c;

void herasu(VVI &a, int i, int j);
int tansaku(VVI a, int i, int j);

int tansaku(VVI a, int i, int j){
//    if (i==0 || i==31 || j==0 || j==31){
//        return 0;
//    }
//    if (a[i][j]==0){
//        return 0;
//    }

    a[i][j]--;

    if (a[i][j]==0){
        return 1;
    }
    int ret = 0;

    if (a[i][j]==a[i+1][j]){
        ret = max(tansaku (a,i+1,j),ret);
    }
    if (a[i][j]==a[i-1][j]){
        ret = max(tansaku (a,i-1,j),ret);
    }
    if (a[i][j]==a[i][j+1]){
        ret = max(tansaku (a,i,j+1),ret);
    }
    if (a[i][j]==a[i][j-1]){
        ret = max(tansaku (a,i,j-1),ret);
    }

    return ret+1;

}

void herasu(VVI &a, int i, int j){
//    if (i==0 || i==31 || j==0 || j==31){
//        return ;
//    }
//    if (a[i][j]==0){
//        return ;
//    }

    a[i][j]--;
    cout << i << " " << j << ENDL;
    c--;
    if (a[i][j]==0){
        return ;
    }

//    int ret = 0,t=0,ts=0;
//    if (a[i][j]==a[i+1][j]){
//        if ((ts=tansaku (a,i+1,j))>ret){
//            ret = ts;
//            t=1;
//        }
//    }
//    if (a[i][j]==a[i-1][j]){
//        if ((ts=tansaku (a,i-1,j))>ret){
//            ret = ts;
//            t=2;
//        }
//    }
//    if (a[i][j]==a[i][j+1]){
//        if ((ts=tansaku (a,i,j+1))>ret){
//            ret = ts;
//            t=3;
//        }
//    }
//    if (a[i][j]==a[i][j-1]){
//        if ((ts=tansaku (a,i,j-1))>ret){
//            ret = ts;
//            t=4;
//        }
//    }
//
//    switch (t){
//        case 1:
//            herasu (a,i+1,j);
//        case 2:
//            herasu (a,i-1,j);
//        case 3:
//            herasu (a,i,j+1);
//        case 4:
//            herasu (a,i,j-1);
//    }

    if (a[i][j]==a[i+1][j]){
        herasu (a,i+1,j);
        return;
    }
    if (a[i][j]==a[i][j+1]){
        herasu (a,i,j+1);
        return;
    }
    if (a[i][j]==a[i-1][j]){
        herasu (a,i-1,j);
        return;
    }
    if (a[i][j]==a[i][j-1]){
        herasu (a,i,j-1);
        return;
    }
}

int main(int argc, const char* argv[]) {
    ios::sync_with_stdio(false);
    cout.setf(ios::fixed, ios::floatfield);
    cout.precision(8);
    cin.tie(0);

    VVI a(N+2,vector<int>(N+2));
    c=0;
    FOR (i,1,N+1) {
        FOR (j, 1, N + 1) {
            cin >> a[i][j];
            c+=a[i][j];
        }
    }

    while(c>0){
        priority_queue <pair<int,PII>> q;
        int  ret=0,ti=1,tj=1,t=0;
        FOR (i,1,N+1){
            FOR (j,1,N+1){
                if  (a[i][j]>0) {
                    q.push (MP (a[i][j], MP (i, j)));
                }
            }
        }
//        REP (k,min(200,SZ(q))){
//            if ((t=tansaku (a,q.top ().SND.FST,q.top ().SND.SND))>ret){
//                ti=q.top ().SND.FST;
//                tj=q.top ().SND.SND;
//                ret=t;
//                q.pop ();
//            }
//        }
        herasu(a,q.top ().SND.FST,q.top ().SND.SND);
    }
    return 0;
}

Submission Info

Submission Time
Task A - 高橋君の山崩しゲーム
User NSTomoS
Language C++14 (Clang 3.8.0)
Score 815463
Code Size 4190 Byte
Status AC
Exec Time 345 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 81694 / 100000 81437 / 100000 81884 / 100000 81033 / 100000 81396 / 100000 81474 / 100000 82056 / 100000 81605 / 100000 81560 / 100000 81324 / 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 339 ms 512 KB
subtask_01_02.txt AC 337 ms 512 KB
subtask_01_03.txt AC 329 ms 512 KB
subtask_01_04.txt AC 345 ms 512 KB
subtask_01_05.txt AC 336 ms 512 KB
subtask_01_06.txt AC 336 ms 512 KB
subtask_01_07.txt AC 326 ms 512 KB
subtask_01_08.txt AC 340 ms 512 KB
subtask_01_09.txt AC 336 ms 512 KB
subtask_01_10.txt AC 339 ms 512 KB