Submission #1176456
Source Code Expand
#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);
}
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() {
for (int i=0; i<1000; ++i)
answer.add(move());
answer.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 |
42149 |
Code Size |
3981 Byte |
Status |
AC |
Exec Time |
1689 ms |
Memory |
1280 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 |
1313 / 50000 |
1382 / 50000 |
1634 / 50000 |
1345 / 50000 |
1320 / 50000 |
1313 / 50000 |
1401 / 50000 |
1446 / 50000 |
1341 / 50000 |
1397 / 50000 |
1588 / 50000 |
1454 / 50000 |
1583 / 50000 |
1437 / 50000 |
1370 / 50000 |
1437 / 50000 |
1378 / 50000 |
1378 / 50000 |
1283 / 50000 |
1409 / 50000 |
1260 / 50000 |
1370 / 50000 |
1367 / 50000 |
1250 / 50000 |
1433 / 50000 |
1433 / 50000 |
1484 / 50000 |
1578 / 50000 |
1303 / 50000 |
1462 / 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 |
1624 ms |
1152 KB |
subtask_01_02.txt |
AC |
1616 ms |
1152 KB |
subtask_01_03.txt |
AC |
1629 ms |
1152 KB |
subtask_01_04.txt |
AC |
1615 ms |
1152 KB |
subtask_01_05.txt |
AC |
1611 ms |
1152 KB |
subtask_01_06.txt |
AC |
1656 ms |
1152 KB |
subtask_01_07.txt |
AC |
1652 ms |
1152 KB |
subtask_01_08.txt |
AC |
1614 ms |
1152 KB |
subtask_01_09.txt |
AC |
1639 ms |
1152 KB |
subtask_01_10.txt |
AC |
1613 ms |
1152 KB |
subtask_01_11.txt |
AC |
1626 ms |
1280 KB |
subtask_01_12.txt |
AC |
1607 ms |
1152 KB |
subtask_01_13.txt |
AC |
1606 ms |
1152 KB |
subtask_01_14.txt |
AC |
1648 ms |
1152 KB |
subtask_01_15.txt |
AC |
1602 ms |
1152 KB |
subtask_01_16.txt |
AC |
1616 ms |
1152 KB |
subtask_01_17.txt |
AC |
1621 ms |
1152 KB |
subtask_01_18.txt |
AC |
1605 ms |
1152 KB |
subtask_01_19.txt |
AC |
1595 ms |
1152 KB |
subtask_01_20.txt |
AC |
1689 ms |
1152 KB |
subtask_01_21.txt |
AC |
1612 ms |
1152 KB |
subtask_01_22.txt |
AC |
1606 ms |
1152 KB |
subtask_01_23.txt |
AC |
1662 ms |
1152 KB |
subtask_01_24.txt |
AC |
1595 ms |
1152 KB |
subtask_01_25.txt |
AC |
1611 ms |
1152 KB |
subtask_01_26.txt |
AC |
1633 ms |
1152 KB |
subtask_01_27.txt |
AC |
1630 ms |
1152 KB |
subtask_01_28.txt |
AC |
1591 ms |
1152 KB |
subtask_01_29.txt |
AC |
1602 ms |
1152 KB |
subtask_01_30.txt |
AC |
1615 ms |
1152 KB |