Submission #1176491
Source Code Expand
// TODO: 時間いっぱい回して、一番良かったところをだす。
// TODO: ターンで、確率の変動
// TODO: 盤面で、スコアの評価
#include <iostream>
#include <bitset>
#include <cstdlib>
#include <vector>
#include <memory>
#include <unistd.h>
#include <chrono>
using namespace std;
using namespace chrono;
typedef long long ll;
class Timer {
private:
high_resolution_clock::time_point start;
public:
void begin() { start = high_resolution_clock::now(); }
ll get_clock() { return duration_cast<milliseconds>(high_resolution_clock::now()-start).count(); }
};
unsigned long xorshift() {
shared_ptr<Timer> ptimer(new Timer());
ptimer->begin();
static unsigned long x=ptimer->get_clock(), y=getpid(), z=521388629, w=88675123;
unsigned long t=(x^(x<<11));
x=y; y=z; z=w; w=(w^(w>>19))^(t^(t>>8));
return w;
}
const int dx[] = { 0, 1, 0, -1, 0 };
const int dy[] = { 1, 0, -1, 0, 0 };
const string dir = "DRUL-";
struct P {
int y,x;
P(int y=0, int x=0):y(y), x(x) {}
bool operator==(const P& o) const {
return y==o.y&&x==o.x;
}
bool operator<(const P& o) const {
return y==o.y?x<o.x:y<o.y;
}
void add(int d) {
y+=dy[d];
x+=dx[d];
}
};
struct F {
bitset<30> f[30];
bitset<30>& get(int y) { return f[y]; }
void set(P p) { f[p.y][p.x]=1; }
void set(int y, int x) { set(P(y, x)); }
void reset(P p) { f[p.y][p.x]=0; }
void reset(int y, int x) { reset(P(y, x)); }
int getR(P p) { return f[p.y].count(); }
int getR(int y) { return f[y].count(); }
bool get(P p) { return f[p.y][p.x]; }
bool get(int y, int x) { return f[y][x]; }
};
struct Answer {
vector<string> ans;
void add(string s) { ans.push_back(s); }
void res() {
int n=ans.size();
cout << n << endl;
for (int i=0; i<n; ++i) cout << ans[i] << endl;
}
};
int H, W, K, T;
P S[451], E[451];
F board;
Answer answer;
inline int dist(P& S, int i) {
return abs(S.y-E[i].y)+abs(S.x-E[i].x);
}
inline bool isMove(P& p) {
return (0 <= p.y && p.y < H && 0 <= p.x && p.x < W);
}
inline double getScore(const int& L) {
double Pd = 20;
for (int i=0; i<K; ++i) { Pd += dist(S[i], i); }
double Pr = 10 + 0.01*L;
return 1e7/(Pd*Pr);
}
void input() {
cin >> H >> W >> K >> T;
for (int i=0; i<K; ++i) {
int a, b, c, d;
cin >> a >> b >> c >> d;
a--, b--, c-- ,d--;
S[i] = P(a, b);
E[i] = P(c, d);
board.set(S[i]);
}
}
// 1ターンの動き
string move() {
string res="";
bitset<450> flag;
for (int i=0; i<K; ++i){ flag[i]=1; res += "-"; }
F next;
while (flag.count()) {
int rd = xorshift()%K;
if (!flag[rd]) continue;
flag[rd]=0;
vector<pair<P, int>> m;
if (dist(S[rd], rd) == 0) {
for (int i=0; i<50; ++i) m.push_back({S[rd], 4});
for (int d=0; d<4; ++d) {
P t = S[rd]; t.add(d);
if (isMove(t) && !board.get(t) && !next.get(t)) {
for (int i=0; i<10; ++i) m.push_back({t, d});
}
}
}
else {
for (int i=0; i<1; ++i) m.push_back({S[rd], 4});
for (int d=0; d<4; ++d) {
P t = S[rd]; t.add(d);
if (isMove(t) && !board.get(t) && !next.get(t)) {
if (dist(t, rd) < dist(S[rd], rd)) {
for (int i=0; i<35; ++i) m.push_back({t, d});
}
else {
for (int i=0; i<5; ++i) m.push_back({t, d});
}
}
}
}
pair<P, int> move = m[xorshift()%(m.size())];
next.set(move.first);
S[rd] = move.first;
res[rd] = dir[move.second];
}
F t;
for (int i=0; i<K; ++i) { t.set(S[i]); }
board = t;
return res;
}
void action() {
Timer timer; timer.begin();
double bestScore = 0;
Answer bestAnswer;
for (int i=1; i<=T; ++i) {
answer.add(move());
double t = getScore(i);
if (bestScore < getScore(i)) {
bestAnswer = answer;
bestScore = t;
}
if (timer.get_clock() >= 3800LL) break;
}
bestAnswer.res();
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
input();
action();
}
Submission Info
Submission Time |
|
Task |
B - 日本橋大渋滞 |
User |
dsytk7 |
Language |
C++14 (GCC 5.4.1) |
Score |
52883 |
Code Size |
4608 Byte |
Status |
AC |
Exec Time |
3805 ms |
Memory |
2048 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 |
1876 / 50000 |
1852 / 50000 |
1994 / 50000 |
1777 / 50000 |
1518 / 50000 |
1891 / 50000 |
1496 / 50000 |
1877 / 50000 |
1513 / 50000 |
1805 / 50000 |
1932 / 50000 |
1739 / 50000 |
1803 / 50000 |
1646 / 50000 |
1884 / 50000 |
1948 / 50000 |
1721 / 50000 |
1818 / 50000 |
1515 / 50000 |
1902 / 50000 |
1496 / 50000 |
1724 / 50000 |
1596 / 50000 |
1524 / 50000 |
1898 / 50000 |
1869 / 50000 |
1843 / 50000 |
1739 / 50000 |
1537 / 50000 |
2150 / 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 |
3804 ms |
1792 KB |
subtask_01_02.txt |
AC |
3804 ms |
1792 KB |
subtask_01_03.txt |
AC |
3804 ms |
1792 KB |
subtask_01_04.txt |
AC |
3804 ms |
1792 KB |
subtask_01_05.txt |
AC |
3804 ms |
1920 KB |
subtask_01_06.txt |
AC |
3805 ms |
1792 KB |
subtask_01_07.txt |
AC |
3804 ms |
2048 KB |
subtask_01_08.txt |
AC |
3804 ms |
1792 KB |
subtask_01_09.txt |
AC |
3804 ms |
2048 KB |
subtask_01_10.txt |
AC |
3804 ms |
1792 KB |
subtask_01_11.txt |
AC |
3804 ms |
1792 KB |
subtask_01_12.txt |
AC |
3804 ms |
1920 KB |
subtask_01_13.txt |
AC |
3804 ms |
1920 KB |
subtask_01_14.txt |
AC |
3804 ms |
1920 KB |
subtask_01_15.txt |
AC |
3805 ms |
1792 KB |
subtask_01_16.txt |
AC |
3803 ms |
1792 KB |
subtask_01_17.txt |
AC |
3804 ms |
1920 KB |
subtask_01_18.txt |
AC |
3805 ms |
1792 KB |
subtask_01_19.txt |
AC |
3805 ms |
2048 KB |
subtask_01_20.txt |
AC |
3804 ms |
1792 KB |
subtask_01_21.txt |
AC |
3804 ms |
1920 KB |
subtask_01_22.txt |
AC |
3804 ms |
1920 KB |
subtask_01_23.txt |
AC |
3804 ms |
1920 KB |
subtask_01_24.txt |
AC |
3805 ms |
1920 KB |
subtask_01_25.txt |
AC |
3805 ms |
1792 KB |
subtask_01_26.txt |
AC |
3804 ms |
1920 KB |
subtask_01_27.txt |
AC |
3805 ms |
1792 KB |
subtask_01_28.txt |
AC |
3803 ms |
1792 KB |
subtask_01_29.txt |
AC |
3805 ms |
1920 KB |
subtask_01_30.txt |
AC |
3804 ms |
1792 KB |