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
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
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