Submission #1174311
Source Code Expand
#include <algorithm>
#include <array>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <sstream>
#include <unordered_map>
#include <vector>
#define INF 1000000002486618624LL
#define MOD 1000000007
#define ALL(x) std::begin(x), std::end(x)
#define X(x) ((x) % W2)
#define Y(x) ((x) / W2)
#define XY(x, y) ((y) * W2 + (x))
int H, W, K, T, W2, W2W2;
std::array<int, 450> P, Q, PP;
template<typename T>
using board_t = std::array<T, 1024>;
board_t<char> board;
void debugout(int t)
{
for (int i = 0, p = 0; i < W2; i ++) {
std::cerr << "t=" << t << ' ';
for (int j = 0; j < W2; j ++, p ++)
std::cerr << board[p];
std::cerr << std::endl;
}
}
double hypot(int p, int q)
{
int px = X(p), py = Y(p);
int qx = X(q), qy = Y(q);
return std::hypot(qx - px, qy - py);
}
int manhatten(int p, int q)
{
int px = X(p), py = Y(p);
int qx = X(q), qy = Y(q);
return std::abs(qx - px) + std::abs(qy - py);
}
int main(int argc, char** argv)
{
std::cin.tie(0);
std::ios_base::sync_with_stdio(0);
std::cin >> H >> W >> K >> T;
W2 = W + 2;
W2W2 = W2 * W2;
std::fill(ALL(board), '.');
for (int i = 0; i < W2; i ++)
board[XY(i, 0)] = board[XY(i, W + 1)] = board[XY(0, i)] = board[XY(W + 1, i)] = '#';
std::array<std::pair<int, int>, 450> pairs;
for (int i = 0; i < K; i ++) {
int a, b, c, d;
std::cin >> a >> b >> c >> d;
P[i] = XY(b, a);
Q[i] = XY(d, c);
board[P[i]] = 'X';
int dx = d - W / 2, dy = c - W / 2;
pairs[i].first = dx * dx + dy * dy;
pairs[i].second = i;
}
std::copy(ALL(P), std::begin(PP));
// std::sort(std::begin(pairs), std::begin(pairs) + K, std::greater<std::pair<int, int>>());
std::sort(std::begin(pairs), std::begin(pairs) + K);
std::array<int, 450> indices;
for (int i = 0; i < K; i ++)
indices[i] = pairs[i].second;
debugout(-1);
std::vector<std::string> a;
for (int t = 0; t < T; t ++) {
std::string s = std::string(K, '-');
for (int i = 0; i < K; i ++) {
int index = indices[i];
int p = P[index], px = X(p), py = Y(p), pp;
int q = Q[index], qx = X(q), qy = Y(q);
if (t < 100) {
qx = qx < W / 2 ? 0 : W;
qy = qy < W / 2 ? 0 : W;
}
else if (t % 200 < 50) {
qx = qx < W / 2 ? W : 0;
qy = qy < W / 2 ? W : 0;
}
else if (t % 200 < 100) {
qx = qx < W / 2 ? 0 : W;
qy = qy < W / 2 ? 0 : W;
}
else if (i > (t - 100) / 2 + 50) {
qx = qx < W / 2 ? 0 : W;
qy = qy < W / 2 ? 0 : W;
}
int dx = qx - px, dy = qy - py;
std::vector<std::tuple<double, int, char>> ps;
if (dx < 0 && board[pp = p - 1] == '.') {
ps.emplace_back(hypot(pp, q), pp, 'L');
}
else if (dx > 0 && board[pp = p + 1] == '.') {
ps.emplace_back(hypot(pp, q), pp, 'R');
}
if (dy < 0 && board[pp = p - W2] == '.') {
ps.emplace_back(hypot(pp, q), pp, 'U');
}
else if (dy > 0 && board[pp = p + W2] == '.') {
ps.emplace_back(hypot(pp, q), pp, 'D');
}
if (ps.empty())
continue;
std::sort(ALL(ps));
pp = std::get<1>(ps[0]);
board[p] = '!';
board[P[index] = pp] = 'X';
s[index] = std::get<2>(ps[0]);
}
for (int i = 0; i < K; i ++) {
if (i <= (t - 100) / 4 + 50)
continue;
if (s[i] != '-')
continue;
int p = P[i], px = X(p), py = Y(p), pp;
int q = Q[i], qx = X(q), qy = Y(q);
if (p == q)
continue;
std::vector<std::pair<int, char>> ps;
if (board[pp = p - 1] == '.')
ps.emplace_back(pp, 'L');
if (board[pp = p + 1] == '.')
ps.emplace_back(pp, 'R');
if (board[pp = p - W2] == '.')
ps.emplace_back(pp, 'U');
if (board[pp = p + W2] == '.')
ps.emplace_back(pp, 'D');
if (ps.empty())
continue;
int xi = rand() % ps.size();
pp = ps[xi].first;
board[p] = '!';
board[P[i] = pp] = 'X';
s[i] = ps[xi].second;
}
if (std::count(ALL(s), '-') == K)
break;
a.push_back(s);
#if 0
debugout(t);
#endif
for (int i = 0; i < W2W2; i ++)
if (board[i] == '!')
board[i] = '.';
}
double sp = 0.0;
int tp = -1;
for (int t = 0, size = a.size(); t < size; t ++) {
int Pd = 20;
for (int i = 0; i < K; i ++) {
Pd += manhatten(PP[i], Q[i]);
switch (a[t][i]) {
case 'U':
PP[i] -= W2;
break;
case 'L':
PP[i] -= 1;
break;
case 'D':
PP[i] += W2;
break;
case 'R':
PP[i] += 1;
break;
default:
break;
}
}
double Pt = 10 + t * 0.01;
double s = 1.0e+7 / (Pd * Pt);
if (s > sp) {
sp = s;
tp = t;
}
#if 0
std::cerr << t << ' ' << Pd << ' ' << s << std::endl;
#endif
}
assert(tp >= 0);
a.resize(tp);
std::cerr << "sp=" << sp << " tp=" << tp << std::endl;
std::cout << a.size() << std::endl;
for (const auto& s : a)
std::cout << s << std::endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
B - 日本橋大渋滞 |
User |
agw |
Language |
C++14 (GCC 5.4.1) |
Score |
11533 |
Code Size |
5673 Byte |
Status |
AC |
Exec Time |
51 ms |
Memory |
1508 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 |
363 / 50000 |
390 / 50000 |
291 / 50000 |
377 / 50000 |
468 / 50000 |
349 / 50000 |
424 / 50000 |
374 / 50000 |
332 / 50000 |
441 / 50000 |
356 / 50000 |
333 / 50000 |
487 / 50000 |
419 / 50000 |
331 / 50000 |
502 / 50000 |
347 / 50000 |
352 / 50000 |
437 / 50000 |
339 / 50000 |
396 / 50000 |
417 / 50000 |
465 / 50000 |
410 / 50000 |
353 / 50000 |
335 / 50000 |
360 / 50000 |
416 / 50000 |
360 / 50000 |
309 / 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 |
50 ms |
1332 KB |
subtask_01_02.txt |
AC |
51 ms |
1332 KB |
subtask_01_03.txt |
AC |
50 ms |
1204 KB |
subtask_01_04.txt |
AC |
50 ms |
1328 KB |
subtask_01_05.txt |
AC |
50 ms |
1324 KB |
subtask_01_06.txt |
AC |
50 ms |
1200 KB |
subtask_01_07.txt |
AC |
51 ms |
1328 KB |
subtask_01_08.txt |
AC |
50 ms |
1200 KB |
subtask_01_09.txt |
AC |
50 ms |
1200 KB |
subtask_01_10.txt |
AC |
50 ms |
1332 KB |
subtask_01_11.txt |
AC |
50 ms |
1324 KB |
subtask_01_12.txt |
AC |
51 ms |
1328 KB |
subtask_01_13.txt |
AC |
51 ms |
1332 KB |
subtask_01_14.txt |
AC |
51 ms |
1328 KB |
subtask_01_15.txt |
AC |
50 ms |
1332 KB |
subtask_01_16.txt |
AC |
50 ms |
1332 KB |
subtask_01_17.txt |
AC |
51 ms |
1332 KB |
subtask_01_18.txt |
AC |
50 ms |
1332 KB |
subtask_01_19.txt |
AC |
50 ms |
1328 KB |
subtask_01_20.txt |
AC |
50 ms |
1200 KB |
subtask_01_21.txt |
AC |
50 ms |
1328 KB |
subtask_01_22.txt |
AC |
50 ms |
1332 KB |
subtask_01_23.txt |
AC |
51 ms |
1324 KB |
subtask_01_24.txt |
AC |
50 ms |
1332 KB |
subtask_01_25.txt |
AC |
49 ms |
1332 KB |
subtask_01_26.txt |
AC |
51 ms |
1328 KB |
subtask_01_27.txt |
AC |
51 ms |
1508 KB |
subtask_01_28.txt |
AC |
50 ms |
1332 KB |
subtask_01_29.txt |
AC |
50 ms |
1332 KB |
subtask_01_30.txt |
AC |
50 ms |
1204 KB |