Submission #1173397
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
const int vy[] = {-1, 0, 1, 0, 0}, vx[] = {0, 1, 0, -1, 0};
const string vv = "URDL-";
const int lim = 1000;
int H, W, K, T, A[450], B[450], C[450], D[450];
vector< pair< int, int > > vs;
bool isover(int y, int x)
{
return (y < 0 || y >= H || x < 0 || x >= W);
}
int getCost(int y, int x, int id)
{
return (abs(y - C[id]) + abs(x - D[id]));
}
struct State
{
int S[30][30];
int line;
int score;
vector< vector< char > > dd;
void init()
{
memset(S, -1, sizeof(S));
}
int getScore()
{
int Pd = 20;
for(int i = 0; i < H; i++) {
for(int j = 0; j < W; j++) {
if(~S[i][j]) Pd += abs(C[S[i][j]] - i) + abs(D[S[i][j]] - j);
}
}
double Pt = 10 + (int) line * 0.01;
return ((int) ceil(10000000 / (Pd * Pt)));
}
void Simulate()
{
dd.push_back(vector< char >(K));
int T[30][30];
memset(T, -1, sizeof(T));
random_shuffle(begin(vs), end(vs));
for(auto& pp : vs) {
int j = pp.first;
int k = pp.second;
if(~S[j][k]) {
char flop = '-';
int id = S[j][k];
int smallest = 114514;
for(int l = 0; l < 4; l++) {
int ny = j + vy[l], nx = k + vx[l];
if(isover(ny, nx)) continue;
int curdist = getCost(ny, nx, id);
if(curdist - getCost(j, k, id) == 2) continue;
if(T[ny][nx] == -1 && S[ny][nx] == -1) smallest = min(smallest, curdist);
}
vector< int > ch;
for(int l = 0; l < 4; l++) {
int ny = j + vy[l], nx = k + vx[l];
if(isover(ny, nx)) continue;
int curdist = getCost(ny, nx, id);
if(T[ny][nx] == -1 && S[ny][nx] == -1 && smallest == curdist) ch.push_back(l);
}
if(!ch.empty()) flop = vv[ch[rand() % ch.size()]];
int dir = vv.find(flop);
T[j + vy[dir]][k + vx[dir]] = id;
dd[line][id] = flop;
}
}
swap(S, T);
++line;
score = getScore();
}
void dump()
{
cerr << score << endl;
cout << line << endl;
for(int i = 0; i < line; i++) {
for(int j = 0; j < K; j++) cout << dd[i][j];
cout << endl;
}
}
bool operator<(const State& s) const
{
return(score < s.score);
}
};
State beststate;
void Beam(State now_state)
{
priority_queue< State > now_q[lim + 1];
now_q[0].emplace(now_state);
time_t start = clock();
while((clock() - start) / CLOCKS_PER_SEC < 1) {
for(int tern = 0; tern < lim; tern++) {
if(!now_q[tern].empty()) {
State state = now_q[tern].top();
now_q[tern].pop();
if(state.score > beststate.score) beststate = state;
for(int j = 0; j < 3; j++) {
State nextstate = state;
nextstate.Simulate();
now_q[tern + 1].emplace(nextstate);
}
}
}
}
}
int main()
{
cin >> H >> W >> K >> T;
for(int i = 0; i < H; i++) for(int j = 0; j < W; j++) vs.emplace_back(i, j);
State now_state;
now_state.init();
for(int i = 0; i < K; i++) {
cin >> A[i] >> B[i] >> C[i] >> D[i];
--A[i], --B[i], --C[i], --D[i];
now_state.S[A[i]][B[i]] = i;
}
Beam(now_state);
beststate.dump();
}
Submission Info
Submission Time |
|
Task |
B - 日本橋大渋滞 |
User |
ei13333 |
Language |
C++14 (GCC 5.4.1) |
Score |
32248 |
Code Size |
3385 Byte |
Status |
AC |
Exec Time |
1887 ms |
Memory |
981216 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 |
test_11 |
test_12 |
test_13 |
test_14 |
test_15 |
test_16 |
test_17 |
test_18 |
test_19 |
test_20 |
test_21 |
test_22 |
test_23 |
test_24 |
test_25 |
test_26 |
test_27 |
test_28 |
test_29 |
test_30 |
Score / Max Score |
1154 / 50000 |
1162 / 50000 |
1152 / 50000 |
1049 / 50000 |
981 / 50000 |
1154 / 50000 |
1009 / 50000 |
1056 / 50000 |
1054 / 50000 |
1120 / 50000 |
1144 / 50000 |
1158 / 50000 |
1111 / 50000 |
1155 / 50000 |
1074 / 50000 |
1072 / 50000 |
1004 / 50000 |
1065 / 50000 |
954 / 50000 |
1128 / 50000 |
966 / 50000 |
1116 / 50000 |
1047 / 50000 |
945 / 50000 |
1001 / 50000 |
1176 / 50000 |
1094 / 50000 |
971 / 50000 |
1034 / 50000 |
1142 / 50000 |
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 |
test_11 |
subtask_01_11.txt |
test_12 |
subtask_01_12.txt |
test_13 |
subtask_01_13.txt |
test_14 |
subtask_01_14.txt |
test_15 |
subtask_01_15.txt |
test_16 |
subtask_01_16.txt |
test_17 |
subtask_01_17.txt |
test_18 |
subtask_01_18.txt |
test_19 |
subtask_01_19.txt |
test_20 |
subtask_01_20.txt |
test_21 |
subtask_01_21.txt |
test_22 |
subtask_01_22.txt |
test_23 |
subtask_01_23.txt |
test_24 |
subtask_01_24.txt |
test_25 |
subtask_01_25.txt |
test_26 |
subtask_01_26.txt |
test_27 |
subtask_01_27.txt |
test_28 |
subtask_01_28.txt |
test_29 |
subtask_01_29.txt |
test_30 |
subtask_01_30.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask_01_01.txt |
AC |
1868 ms |
981216 KB |
subtask_01_02.txt |
AC |
1881 ms |
980696 KB |
subtask_01_03.txt |
AC |
1839 ms |
980572 KB |
subtask_01_04.txt |
AC |
1870 ms |
980640 KB |
subtask_01_05.txt |
AC |
1868 ms |
980832 KB |
subtask_01_06.txt |
AC |
1871 ms |
980708 KB |
subtask_01_07.txt |
AC |
1871 ms |
980760 KB |
subtask_01_08.txt |
AC |
1867 ms |
980756 KB |
subtask_01_09.txt |
AC |
1874 ms |
980668 KB |
subtask_01_10.txt |
AC |
1871 ms |
980812 KB |
subtask_01_11.txt |
AC |
1876 ms |
980740 KB |
subtask_01_12.txt |
AC |
1865 ms |
980788 KB |
subtask_01_13.txt |
AC |
1884 ms |
980800 KB |
subtask_01_14.txt |
AC |
1887 ms |
980760 KB |
subtask_01_15.txt |
AC |
1871 ms |
980848 KB |
subtask_01_16.txt |
AC |
1865 ms |
980788 KB |
subtask_01_17.txt |
AC |
1866 ms |
980852 KB |
subtask_01_18.txt |
AC |
1865 ms |
980832 KB |
subtask_01_19.txt |
AC |
1868 ms |
980760 KB |
subtask_01_20.txt |
AC |
1853 ms |
980728 KB |
subtask_01_21.txt |
AC |
1873 ms |
980752 KB |
subtask_01_22.txt |
AC |
1873 ms |
980784 KB |
subtask_01_23.txt |
AC |
1871 ms |
980828 KB |
subtask_01_24.txt |
AC |
1861 ms |
980808 KB |
subtask_01_25.txt |
AC |
1878 ms |
980772 KB |
subtask_01_26.txt |
AC |
1871 ms |
980668 KB |
subtask_01_27.txt |
AC |
1874 ms |
980676 KB |
subtask_01_28.txt |
AC |
1864 ms |
980872 KB |
subtask_01_29.txt |
AC |
1874 ms |
980720 KB |
subtask_01_30.txt |
AC |
1869 ms |
980696 KB |