Submission #8243543
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>
#include <sys/time.h>
#include <random>
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<int, P> T;
class Timer{
protected:
double startTime;
double limit;
bool alreadyTimeup;
public:
Timer(double timeLimit){
set(timeLimit);
}
void set(double time_limit){
limit = time_limit;
startTime = now();
alreadyTimeup = false;
}
bool timeup(){
if(alreadyTimeup) return true;
if(now() - startTime > limit){
alreadyTimeup = true;
return true;
}else{
return false;
}
}
double elapse(){
return now() - startTime;
}
double used(){
return elapse() / limit;
}
protected:
double now(){
timeval tv;
gettimeofday(&tv, 0);
return tv.tv_sec + tv.tv_usec * 1e-6;
}
};
P operator + (const P & l,const P & r){
return {l.fs + r.fs, l.sc + r.sc};
}
Timer timer(9.0);
mt19937 rand_gen(12453);
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] = true;
}
}
for(int i = 1; i <= h; i++){
for(int j = 1; j <= w; j++){
state[i][j] = false;
}
}
}
int getValue(P c){
return a[c.fs][c.sc];
}
bool changeState(P x){
if(x.fs != -1 && x.sc != -1) {
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;
double r = rand_gen() / (1.0 + mt19937::max());
vector<P> okList;
for (auto dir: v) {
P next = c + dir;
if(!reached(next) && getValue(next) < getValue(c)){
okList.emplace_back(next);
if(getValue(next) > ma){
ret = next;
ma = getValue(next);
}
}
}
if(okList.empty()){
return ret;
}
if(r <= 0.1){
int x = rand_gen() % okList.size();
ret = okList[x];
}
return ret;
}
vector<vector<P>> explore(vector<vector<P>> res, int count){
int su = 0;
if(count == 1367){
int x = 0;
}
for(auto path: res){
for(auto c: path) {
changeState(c);
su++;
}
}
vector<P> tmpPath;
while(true) {
if(su == h * w){
break;
}
// 新たなパスを追加
for(int i = 0; i < h * w; i++){
if(reached(sorted[i].sc)){
continue;
}
tmpPath.clear();
tmpPath.emplace_back(sorted[i].sc);
changeState(sorted[i].sc);
su++;
break;
}
while(true) {
auto itr = --(tmpPath.end());
P next = select(*itr);
if (next.fs == -1 && next.sc == -1) {
break;
}
tmpPath.emplace_back(next);
su++;
changeState(next);
}
res.push_back(tmpPath);
}
return res;
}
void solve(){
int count = 0;
vector<vector<P>> bestResult;
int bestScore = INT32_MAX;
while(true) {
init();
count++;
// cerr << count << endl;
if(count % 500 == 0) {
double time_used = timer.used();
if (time_used >= 1.0 - 1e-11) {
break;
}
}
vector<vector<P>> initialRes;
if(count > 1){
int x = count / 1000;
for(int i = 0; i < x && bestResult.size() > i; i++){
initialRes.push_back(bestResult[i]);
}
}
vector<vector<P>> exploreResult = explore(initialRes, count);
int score = calcScore(exploreResult);
if(score < bestScore){
bestResult = exploreResult;
bestScore = score;
cerr << bestScore << endl;
}
}
outputResult(bestResult);
cerr << count << endl;
checkResult();
}
int calcScore(vector<vector<P> > v){
int res = 0;
for(auto w: v){
res += getValue(*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 |
786782 |
Code Size |
7490 Byte |
Status |
AC |
Exec Time |
9158 ms |
Memory |
640 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 |
78739 / 100000 |
78056 / 100000 |
78818 / 100000 |
78168 / 100000 |
78268 / 100000 |
78887 / 100000 |
79020 / 100000 |
79087 / 100000 |
78993 / 100000 |
78746 / 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 |
9102 ms |
640 KB |
subtask_01_02.txt |
AC |
9093 ms |
640 KB |
subtask_01_03.txt |
AC |
9084 ms |
640 KB |
subtask_01_04.txt |
AC |
9095 ms |
640 KB |
subtask_01_05.txt |
AC |
9158 ms |
640 KB |
subtask_01_06.txt |
AC |
9078 ms |
640 KB |
subtask_01_07.txt |
AC |
9089 ms |
640 KB |
subtask_01_08.txt |
AC |
9100 ms |
640 KB |
subtask_01_09.txt |
AC |
9120 ms |
640 KB |
subtask_01_10.txt |
AC |
9132 ms |
640 KB |