Submission #1678346
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
typedef vector<int> Vi;
//typedef tuple<int, int, int> T;
#define FOR(i,s,x) for(int i=s;i<(int)(x);i++)
#define REP(i,x) FOR(i,0,x)
#define ALL(c) c.begin(), c.end()
#define DUMP( x ) cerr << #x << " = " << ( x ) << endl
const int dr[4] = {-1, 0, 1, 0};
const int dc[4] = {0, 1, 0, -1};
const int N = 50, W = 20, C = 150;
const double TL = 9.675;
int M = 0;
int B[50][50]; // 0->. 1->o 2->x 3->+ 4->-
int board[50][50], used[50][50];
pair<int, int> D[2500]; // 変更可能な座標
const string S = ".ox+-";
void dump() {
// print result
REP(i, N) {
REP(j, N) printf("%c", S[B[i][j]]);
printf("\n");
}
}
void drop() {
// simulate board
REP(c, N) {
for (int r = N - 1; r >= 0; r--) {
if (board[r][c] == 0) {
int now = r;
while (now >= 0 and board[now][c] == 0) now--;
if (now < 0) break;
if (board[now][c] == 4) {
r = now;
continue;
}
while (now >= 0 and board[now][c] != 0 and board[now][c] != 4) {
board[r][c] = board[now][c];
board[now][c] = 0;
now--, r--;
}
if (now < 0) break;
if (board[now][c] == 4) {
r = now;
continue;
}
r++;
}
}
}
}
int bfs(int sr, int sc, char s) {
queue<pair<int, int>> que;
que.emplace(sr, sc);
int cnt = 0;
while (not que.empty()) {
int r, c; tie(r, c) = que.front(); que.pop();
if (used[r][c]) continue;
cnt++;
used[r][c] = 1;
REP(i, 4) {
int nr = r + dr[i], nc = c + dc[i];
if (0 <= nr and nr < N and 0 <= nc and nc < N and not used[nr][nc] and board[nr][nc] == s) {
que.emplace(nr, nc);
}
}
}
return cnt;
}
int evaluate(vector<int> change) {
REP(i, N) REP(j, N) board[i][j] = B[i][j];
REP(i, M) {
int r, c; tie(r, c) = D[i];
if (change[i] == 1) board[r][c] = 3;
if (change[i] == 2) board[r][c] = 4;
}
drop();
memset(used, 0, sizeof(used));
int max_o = 0, max_x = 0;
REP(r, N) REP(c, N) {
if (used[r][c]) continue;
if (board[r][c] == 1) max_o = max(max_o, bfs(r, c, 1));
if (board[r][c] == 2) max_x = max(max_x, bfs(r, c, 2));
}
return max_o + max_x;
}
void solve() {
chrono::system_clock::time_point start = chrono::system_clock::now();
random_device rnd;
mt19937 mt(rnd());
for (int i = N - 1; i >= 0; i--) {
for (int j = 0; j < N; j++) {
if (B[i][j] == 0) D[M] = make_pair(i, j), M++;
}
}
vector<int> best_change(M, 0);
vector<vector<int>> best_changes;
REP(i, W) best_changes.push_back(best_change);
vector<int> best_scores(W);
REP(i, W) best_scores[i] = evaluate(best_changes[i]);
uniform_int_distribution<> rand3(0, 2), randM(0, M-1), rand10(1, 10);
int itr = 0;
while (true) {
double diff = chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now() - start).count() / 1000.;
if (diff > TL) break;
vector<vector<int>> changes;
vector<pair<int, int>> ranks;
REP(i, W) ranks.emplace_back(-best_scores[i], i), changes.push_back(best_changes[i]);
REP(i, W) {
REP(_, C) {
vector<int> change = best_changes[i];
int change_num = 5;
REP(_, change_num) {
int idx = randM(mt) / 2;
int ns = rand3(mt);
change[idx] = ns;
}
int score = evaluate(change);
ranks.emplace_back(-score, changes.size());
changes.push_back(change);
}
}
sort(ALL(ranks));
REP(i, W) best_changes[i] = changes[ranks[i].second], best_scores[i] = -ranks[i].first;
//cerr << chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now() - start).count() / 1000. << ' ' << itr << ' ' << best_scores[0] << endl;
itr++;
}
cerr << itr << ' ' << best_scores[0] << endl;
best_change = best_changes[0];
REP(i, M) {
int r, c; tie(r, c) = D[i];
if (best_change[i] == 1) B[r][c] = 3;
if (best_change[i] == 2) B[r][c] = 4;
}
dump();
}
int main() {
REP(i, N) {
string row; cin >> row;
REP(j, N) {
if (row[j] == '.') {
B[i][j] = 0;
} else if (row[j] == 'o') {
B[i][j] = 1;
} else if (row[j] == 'x') {
B[i][j] = 2;
}
}
}
solve();
return 0;
}
Submission Info
Submission Time |
|
Task |
A - ○×ブロック |
User |
n_knuu |
Language |
C++14 (GCC 5.4.1) |
Score |
5510 |
Code Size |
4543 Byte |
Status |
AC |
Exec Time |
9939 ms |
Memory |
15820 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 |
502 / 2500 |
547 / 2500 |
545 / 2500 |
557 / 2500 |
672 / 2500 |
523 / 2500 |
516 / 2500 |
494 / 2500 |
562 / 2500 |
592 / 2500 |
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 |
9715 ms |
15672 KB |
subtask_01_02.txt |
AC |
9882 ms |
15232 KB |
subtask_01_03.txt |
AC |
9735 ms |
15360 KB |
subtask_01_04.txt |
AC |
9793 ms |
15820 KB |
subtask_01_05.txt |
AC |
9888 ms |
15180 KB |
subtask_01_06.txt |
AC |
9751 ms |
15248 KB |
subtask_01_07.txt |
AC |
9885 ms |
15360 KB |
subtask_01_08.txt |
AC |
9703 ms |
15620 KB |
subtask_01_09.txt |
AC |
9939 ms |
15484 KB |
subtask_01_10.txt |
AC |
9872 ms |
15328 KB |