Submission #1175157
Source Code Expand
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;
#ifdef _WIN32
#include <Windows.h>
#else
#include <sys/time.h>
#endif
class TicToc
{
private:
double getCurrTime(){
#ifdef _WIN32
return GetTickCount() * 1e-3;
#else
struct timeval tv;
gettimeofday(&tv, NULL);
return tv.tv_sec + tv.tv_usec * 1e-6;
#endif
}
double startTime;
public:
void tic(){
startTime = getCurrTime();
}
double toc(){
return getCurrTime() - startTime;
}
};
unsigned xor128(){
static unsigned x=123456789,y=362436069,z=521288629,w=88675123;
unsigned t;
t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
}
void shuffle(vector<int>& v)
{
int n = v.size();
for(int i=0; i<n; ++i){
int j = i + xor128() % (n - i);
swap(v[i], v[j]);
}
}
double getScore(const vector<int>& gy, const vector<int>& gx, const vector<int>& y, const vector<int>& x, int l)
{
int n = gy.size();
int pd = 20;
for(int i=0; i<n; ++i)
pd += abs(gy[i] - y[i]) + abs(gx[i] - x[i]);
double pt = 10 + l * 0.01;
double score = 1.0e7 / (pd * pt);
return score;
}
const int dy[] = {-1, 1, 0, 0};
const int dx[] = {0, 0, -1, 1};
const string ds = "UDLR";
int main()
{
int h, w, n, maxTurn;
cin >> h >> w >> n >> maxTurn;
maxTurn = min(maxTurn, 1200);
vector<int> sy(n), sx(n), gy(n), gx(n);
for(int i=0; i<n; ++i){
cin >> sy[i] >> sx[i] >> gy[i] >> gx[i];
-- sy[i];
-- sx[i];
-- gy[i];
-- gx[i];
}
double allBestScore = 0.0;
vector<string> ans;
TicToc tictoc;
tictoc.tic();
while(tictoc.toc() < 3.5){
vector<int> y = sy;
vector<int> x = sx;
vector<vector<int> > pos(h, vector<int>(w, 0));
for(int i=0; i<n; ++i)
pos[sy[i]][sx[i]] = 1;
vector<string> act(maxTurn, string(n, '-'));
vector<int> index(n);
vector<int> d(4);
for(int i=0; i<n; ++i)
index[i] = i;
for(int i=0; i<4; ++i)
d[i] = i;
int bestTurn = 0;
double bestScore = getScore(gy, gx, y, x, 0);
string lastAct;
for(int turn=1; turn<=maxTurn; ++turn){
shuffle(index);
vector<int> yy = y;
vector<int> xx = x;
vector<vector<int> > pos2 = pos;
string act2(n, '-');
for(int i : index){
shuffle(d);
for(int k : d){
int y2 = yy[i] + dy[k];
int x2 = xx[i] + dx[k];
if(!(0 <= y2 && y2 < h && 0 <= x2 && x2 < w))
continue;
if(pos2[y2][x2] >= turn)
continue;
if(abs(gy[i] - y2) + abs(gx[i] - x2) < abs(gy[i] - yy[i]) + abs(gx[i] - xx[i])){
act2[i] = ds[k];
yy[i] = y2;
xx[i] = x2;
break;
}
}
pos2[yy[i]][xx[i]] = turn + 1;
}
double score = getScore(gy, gx, yy, xx, turn);
if(bestScore < score){
bestTurn = turn;
bestScore = score;
lastAct = act2;
}
for(int i : index){
shuffle(d);
bool isMove = false;
for(int k : d){
int y2 = y[i] + dy[k];
int x2 = x[i] + dx[k];
if(!(0 <= y2 && y2 < h && 0 <= x2 && x2 < w))
continue;
if(pos[y2][x2] >= turn)
continue;
if(abs(gy[i] - y2) + abs(gx[i] - x2) < abs(gy[i] - y[i]) + abs(gx[i] - x[i])){
act[turn-1][i] = ds[k];
y[i] = y2;
x[i] = x2;
isMove = true;
break;
}
}
if(!isMove){ /*遠ざかる方向にも移動 */
shuffle(d);
for(int k : d){
int y2 = y[i] + dy[k];
int x2 = x[i] + dx[k];
if(!(0 <= y2 && y2 < h && 0 <= x2 && x2 < w))
continue;
if(pos[y2][x2] >= turn)
continue;
act[turn-1][i] = ds[k];
y[i] = y2;
x[i] = x2;
break;
}
}
pos[y[i]][x[i]] = turn + 1;
}
}
if(allBestScore < bestScore){
allBestScore = bestScore;
act.resize(bestTurn);
act.back() = lastAct;
ans.swap(act);
}
cerr << tictoc.toc() << endl;
}
cout << ans.size() << endl;
for(const string& s : ans)
cout << s << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
B - 日本橋大渋滞 |
User |
mamekin |
Language |
C++14 (GCC 5.4.1) |
Score |
49539 |
Code Size |
5676 Byte |
Status |
AC |
Exec Time |
3588 ms |
Memory |
1792 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 |
1770 / 50000 |
1868 / 50000 |
1747 / 50000 |
1623 / 50000 |
1405 / 50000 |
1795 / 50000 |
1502 / 50000 |
1587 / 50000 |
1692 / 50000 |
1754 / 50000 |
1696 / 50000 |
1761 / 50000 |
1689 / 50000 |
1703 / 50000 |
1587 / 50000 |
1807 / 50000 |
1691 / 50000 |
1580 / 50000 |
1425 / 50000 |
1663 / 50000 |
1523 / 50000 |
1673 / 50000 |
1668 / 50000 |
1444 / 50000 |
1628 / 50000 |
1763 / 50000 |
1639 / 50000 |
1638 / 50000 |
1581 / 50000 |
1637 / 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 |
3554 ms |
1540 KB |
subtask_01_02.txt |
AC |
3585 ms |
1292 KB |
subtask_01_03.txt |
AC |
3574 ms |
1428 KB |
subtask_01_04.txt |
AC |
3559 ms |
1452 KB |
subtask_01_05.txt |
AC |
3539 ms |
1372 KB |
subtask_01_06.txt |
AC |
3550 ms |
1456 KB |
subtask_01_07.txt |
AC |
3523 ms |
1408 KB |
subtask_01_08.txt |
AC |
3554 ms |
1524 KB |
subtask_01_09.txt |
AC |
3541 ms |
1592 KB |
subtask_01_10.txt |
AC |
3528 ms |
1476 KB |
subtask_01_11.txt |
AC |
3547 ms |
1656 KB |
subtask_01_12.txt |
AC |
3555 ms |
1492 KB |
subtask_01_13.txt |
AC |
3554 ms |
1408 KB |
subtask_01_14.txt |
AC |
3567 ms |
1508 KB |
subtask_01_15.txt |
AC |
3558 ms |
1356 KB |
subtask_01_16.txt |
AC |
3575 ms |
1440 KB |
subtask_01_17.txt |
AC |
3568 ms |
1616 KB |
subtask_01_18.txt |
AC |
3525 ms |
1716 KB |
subtask_01_19.txt |
AC |
3588 ms |
1792 KB |
subtask_01_20.txt |
AC |
3547 ms |
1408 KB |
subtask_01_21.txt |
AC |
3537 ms |
1472 KB |
subtask_01_22.txt |
AC |
3544 ms |
1628 KB |
subtask_01_23.txt |
AC |
3534 ms |
1748 KB |
subtask_01_24.txt |
AC |
3513 ms |
1780 KB |
subtask_01_25.txt |
AC |
3562 ms |
1364 KB |
subtask_01_26.txt |
AC |
3553 ms |
1476 KB |
subtask_01_27.txt |
AC |
3561 ms |
1704 KB |
subtask_01_28.txt |
AC |
3522 ms |
1344 KB |
subtask_01_29.txt |
AC |
3535 ms |
1392 KB |
subtask_01_30.txt |
AC |
3562 ms |
1448 KB |