Submission #1174191
Source Code Expand
#define DINGER_GISBAR
#include <bits/stdc++.h>
using namespace std;
const long long MOD = static_cast<int>(1e9) + 7;
//{{{TEMPLATE_BEGIN
#include <unistd.h>
using namespace std::rel_ops;
#ifdef ZEROKUGI
#include <dumper.hpp>
#define dump(x) dumper::dumper(cerr, __LINE__, (#x), (x), 50, 1, 1)
#define tick(...) dumper::tick(__VA_ARGS__)
#pragma message "Compiling " __FILE__
#else
#define dump(x)
#define tick(...)
#endif
typedef long long lint;
typedef unsigned long long ulint;
typedef long double ldouble;
typedef vector<int> vint;
#define rep(i, n) \
for (int i = 0, i##_len = static_cast<int>(n); i < i##_len; i++)
#define all(c) begin(c), end(c)
#define perm(c) \
sort(all(c)); \
for (bool c##p = 1; c##p; c##p = next_permutation(all(c)))
#define uniquenize(v) (v).erase(unique(all(v)), end(v))
#define cauto const auto&
#define memset(x, y) memset(x, y, sizeof(x))
#define popcount __builtin_popcount
#define gcd __gcd
inline lint bit(int x) { return 1LL << x; }
template <class T>
inline int size(const T& a) {
return (int)a.size();
}
template <class T>
inline bool chmin(T& a, const T& b) {
return a > b ? a = b, 1 : 0;
}
template <class T>
inline int clamp(T v, T lo, T hi) {
return (v > hi) - (v < lo);
}
template <class T>
inline bool chmax(T& a, const T& b) {
return a < b ? a = b, 1 : 0;
}
template <class T>
inline pair<vector<T>, char> operator*(const vector<T>& v, const char& c) {
return make_pair(v, c);
}
template <class T>
inline istream& operator>>(istream& is, vector<T>& v) {
#ifdef ZEROKUGI
if (v.empty()) {
cerr << "Error L" << __LINE__ << ": vector size is zero." << endl;
exit(EXIT_FAILURE);
}
#endif
for (auto& x : v) is >> x;
return is;
}
template <class T>
inline ostream& operator<<(ostream& os, const pair<vector<T>, char>& v) {
bool t = 0;
for (const T& x : v.first) {
if (t) os << v.second;
os << x;
t = 1;
}
return os;
}
template <class T>
inline ostream& operator<<(ostream& os, vector<T>& v) {
return os << v * ' ';
}
struct before_main {
before_main() {
cin.tie(0);
ios::sync_with_stdio(0);
cout << fixed << setprecision(20);
tick(0, 0);
};
} __before_main;
//}}}TEMPLATE_END
int h, w, k, t;
int a[555], b[555], c[555], d[555], e[555], f[555];
bool field[50][50];
bool nxt[50][50];
vector<char> mov[555];
bool ok(int y, int x) {
if (y < 0 || y >= 30) return false;
if (x < 0 || x >= 30) return false;
return !field[y][x] && !nxt[y][x];
}
vector<int> vvvvvv() {
vector<int> v(450);
iota(all(v), 0);
random_shuffle(all(v));
return v;
}
void tate() {
memset(nxt, 0);
memset(field, 0);
rep(i, k) field[a[i]][b[i]] = true;
rep(i, k) {
int dy;
if (a[i] < e[i]) {
dy = 1;
} else if (a[i] > e[i]) {
dy = -1;
} else {
dy = 0;
}
if (!ok(a[i] + dy, b[i])) dy = 0;
a[i] += dy;
nxt[a[i]][b[i]] = true;
char c;
if (dy == 1) {
c = 'D';
} else if (dy == 0) {
c = '-';
} else {
c = 'U';
}
mov[i].push_back(c);
}
}
void yoko() {
memset(nxt, 0);
memset(field, 0);
rep(i, k) field[a[i]][b[i]] = true;
for(int i: vvvvvv()){
int dx;
if (b[i] < f[i]) {
dx = 1;
} else if (b[i] > f[i]) {
dx = -1;
} else {
dx = 0;
}
if (!ok(a[i], b[i] + dx)) dx = 0;
b[i] += dx;
nxt[a[i]][b[i]] = true;
char c;
if (dx == 1) {
c = 'R';
} else if (dx == 0) {
c = '-';
} else {
c = 'L';
}
mov[i].push_back(c);
}
}
int dya[] = {0, 1, 0, -1};
int dxa[] = {1, 0, -1, 0};
void aaaa() {
memset(nxt, 0);
memset(field, 0);
rep(i, k) field[a[i]][b[i]] = true;
for (int i : vvvvvv()) {
int dir = rand() % 4;
int dy = dya[dir];
int dx = dxa[dir];
if (!ok(a[i] + dy, b[i] + dx)) {
dx = 0;
dy = 0;
}
b[i] += dx;
a[i] += dy;
nxt[a[i]][b[i]] = true;
char c;
if (dy == 1) {
c = 'D';
} else if (dy == -1) {
c = 'U';
} else if (dx == 1) {
c = 'R';
} else if (dx == -1) {
c = 'L';
} else {
c = '-';
}
mov[i].push_back(c);
}
}
void bbbb() {
memset(nxt, 0);
memset(field, 0);
rep(i, k) field[a[i]][b[i]] = true;
rep(i, k) {
int dir = rand() % 4;
int dy = dya[dir];
int dx = dxa[dir];
if (!ok(a[i] + dy, b[i] + dx)) {
dx = 0;
dy = 0;
}
b[i] += dx;
a[i] += dy;
nxt[a[i]][b[i]] = true;
char c;
if (dy == 1) {
c = 'D';
} else if (dy == -1) {
c = 'U';
} else if (dx == 1) {
c = 'R';
} else if (dx == -1) {
c = 'L';
} else {
c = '-';
}
mov[i].push_back(c);
}
}
int main() {
cin >> h >> w >> k >> t;
rep(i, k) cin >> a[i] >> b[i] >> c[i] >> d[i];
rep(i, k) {
a[i]--;
b[i]--;
c[i]--;
d[i]--;
field[a[i]][b[i]] = true;
}
rep(aaa, 100) {
// random
rep(i, 3) aaaa();
// tate
rep(i, k) {
f[i] = d[i];
if (b[i] / 3 < d[i] / 3) {
e[i] = a[i] / 6 * 6 + rand() % 2;
} else if (b[i] / 3 > d[i] / 3) {
e[i] = a[i] / 6 * 6 + 2 + rand() % 2;
} else {
e[i] = a[i] / 6 * 6 + 4 + rand() % 2;
}
}
rep(_, 3) { tate(); }
rep(_, 3) { yoko(); }
// yoko
rep(i, k) {
e[i] = c[i];
if (a[i] / 3 < c[i] / 3) {
f[i] = b[i] / 6 * 6 + rand() % 2;
} else if (a[i] / 3 > c[i] / 3) {
f[i] = b[i] / 6 * 6 + 2 + rand() % 2;
} else {
f[i] = b[i] / 6 * 6 + 4 + rand() % 2;
}
}
rep(_, 3) { yoko(); }
rep(_, 3) { tate(); }
}
int len = mov[0].size();
cout << len << endl;
rep(i, len) {
rep(j, k) { cout << mov[j][i]; }
cout << endl;
}
}
Submission Info
Submission Time |
|
Task |
B - 日本橋大渋滞 |
User |
eha |
Language |
C++14 (GCC 5.4.1) |
Score |
6622 |
Code Size |
6769 Byte |
Status |
AC |
Exec Time |
42 ms |
Memory |
1920 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 |
212 / 50000 |
251 / 50000 |
258 / 50000 |
229 / 50000 |
236 / 50000 |
231 / 50000 |
206 / 50000 |
248 / 50000 |
241 / 50000 |
242 / 50000 |
228 / 50000 |
206 / 50000 |
214 / 50000 |
206 / 50000 |
211 / 50000 |
204 / 50000 |
213 / 50000 |
166 / 50000 |
183 / 50000 |
243 / 50000 |
164 / 50000 |
221 / 50000 |
197 / 50000 |
202 / 50000 |
210 / 50000 |
235 / 50000 |
231 / 50000 |
262 / 50000 |
218 / 50000 |
254 / 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 |
41 ms |
1920 KB |
subtask_01_02.txt |
AC |
41 ms |
1920 KB |
subtask_01_03.txt |
AC |
41 ms |
1920 KB |
subtask_01_04.txt |
AC |
41 ms |
1920 KB |
subtask_01_05.txt |
AC |
41 ms |
1920 KB |
subtask_01_06.txt |
AC |
41 ms |
1920 KB |
subtask_01_07.txt |
AC |
41 ms |
1920 KB |
subtask_01_08.txt |
AC |
41 ms |
1920 KB |
subtask_01_09.txt |
AC |
41 ms |
1920 KB |
subtask_01_10.txt |
AC |
41 ms |
1920 KB |
subtask_01_11.txt |
AC |
41 ms |
1920 KB |
subtask_01_12.txt |
AC |
42 ms |
1920 KB |
subtask_01_13.txt |
AC |
42 ms |
1920 KB |
subtask_01_14.txt |
AC |
41 ms |
1920 KB |
subtask_01_15.txt |
AC |
41 ms |
1920 KB |
subtask_01_16.txt |
AC |
41 ms |
1920 KB |
subtask_01_17.txt |
AC |
41 ms |
1920 KB |
subtask_01_18.txt |
AC |
41 ms |
1920 KB |
subtask_01_19.txt |
AC |
41 ms |
1920 KB |
subtask_01_20.txt |
AC |
41 ms |
1920 KB |
subtask_01_21.txt |
AC |
41 ms |
1920 KB |
subtask_01_22.txt |
AC |
42 ms |
1920 KB |
subtask_01_23.txt |
AC |
41 ms |
1920 KB |
subtask_01_24.txt |
AC |
41 ms |
1920 KB |
subtask_01_25.txt |
AC |
41 ms |
1920 KB |
subtask_01_26.txt |
AC |
41 ms |
1920 KB |
subtask_01_27.txt |
AC |
41 ms |
1920 KB |
subtask_01_28.txt |
AC |
41 ms |
1920 KB |
subtask_01_29.txt |
AC |
41 ms |
1920 KB |
subtask_01_30.txt |
AC |
41 ms |
1920 KB |