Submission #8242687


Source Code Expand

#include <iostream>
#include <algorithm>
#include <vector>
#include<string>
#include <set>
#include <map>
#include <queue>
#include <limits.h>
#include <bitset>

using namespace std;

#define rip(i, n, s) for (int i = (s);i < ( int )( n ); i++)
#define all(a) (a).begin(), (a).end()
typedef long long ll;
typedef pair<int, int> P;

int n = 31;
vector<vector<int>> direct = {{0,1},{1,0},{0,-1},{-1,0}};
vector<vector<int>> da(32, vector<int>(32,0));
priority_queue<pair<int, int>> pq;
vector<P> ans;

/*int chane(vector<vector<int>> &co,int x,int y){
	int ma=0;
	if(co[x][y]>-1){
		return co[x][y];
	}
	rip(i,4,0){
		if(da[x][y]==da[x+direct[i][0]][y+direct[i][1]]+1){
			ma=max(ma,chane(co,x+direct[i][0],y+direct[i][1]));
		}
	}
	co[x][y]=ma;
	return ma;
}*/

void dfs(int x, int y) {
	ans.push_back(make_pair(x, y));
	da[x][y]--;
	if (da[x][y] == 0) {
		return;
	}
	pq.push(make_pair(da[x][y], x*n + y));
	rip(i, 4, 0) {
		if (da[x][y] == da[x + direct[i][0]][y + direct[i][1]]) {
			dfs(x + direct[i][0], y + direct[i][1]);
			return;
		}
	}
	return;
}

void output() {
	int size = ans.size();
	//cout << size << endl;

	rip(i, size, 0) {
		printf("%d %d\n", ans[i].first, ans[i].second);
	}
}

int main() {
	rip(i, n, 1) {
		rip(j, n, 1) {
			cin >> da[i][j];
		}
	}
	/*vector<vector<int>> co(n,vector<int>(n,-1));
	priority_queue<pair<int,int>> pq;
	rip(i,n,0){
		rip(j,n,0){
			pq.push=make_pair(chane(co,i,j),i*n+j);
		}
	}*/
	rip(i, n, 1) {
		rip(j, n, 1) {
			pq.push(make_pair(da[i][j], i*n + j));
		}
	}
	while (!pq.empty()) {
		P now = pq.top();
		pq.pop();
		if (da[now.second / n][now.second%n] == now.first) {
			dfs(now.second / n, now.second%n);
		}
	}
	output();
}

Submission Info

Submission Time
Task A - 高橋君の山崩しゲーム
User sapphire15
Language C++14 (GCC 5.4.1)
Score 812809
Code Size 1772 Byte
Status AC
Exec Time 14 ms
Memory 1044 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 81483 / 100000 81288 / 100000 81791 / 100000 80449 / 100000 81242 / 100000 81038 / 100000 81602 / 100000 81389 / 100000 81378 / 100000 81149 / 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 13 ms 1044 KB
subtask_01_02.txt AC 13 ms 1044 KB
subtask_01_03.txt AC 13 ms 1044 KB
subtask_01_04.txt AC 14 ms 1044 KB
subtask_01_05.txt AC 13 ms 1044 KB
subtask_01_06.txt AC 13 ms 1044 KB
subtask_01_07.txt AC 13 ms 1044 KB
subtask_01_08.txt AC 13 ms 1044 KB
subtask_01_09.txt AC 13 ms 1044 KB
subtask_01_10.txt AC 13 ms 1044 KB