Submission #1173709


Source Code Expand

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

// c++11
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>

#define mp make_pair
#define mt make_tuple
#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

const int dx[] = {0, +1, 0, -1, 0};
const int dy[] = {-1, 0, +1, 0, 0};
const string DIRS = "URDL-";
const int MAX_HW = 30;
class XorShift {
  static const int MAX = numeric_limits<int>::max();
  int x = 123456789, y = 362436069, z = 521288629, w = 88675123;

public:
  XorShift() {}
  XorShift(int seed) {
    x ^= seed;
    y ^= x << 10 & seed;
    w ^= y >> 20 | seed;
    z ^= w & x;
  }
  int next() {
    int t = x ^ (x << 11);
    x = y;
    y = z;
    z = w;
    return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
  }
  int next(int min_value, int max_value) {
    int range = max_value - min_value;
    return (sample() * range) + min_value;
  }
  double sample() { return next() * 1.0 / MAX; }
} rnd;
//get millsec
#include <sys/time.h>
class Timer {
public:
  Timer() {}
  void start() { start_time = get_mill_sec(); }
  //millsec
  double get_duration() { return get_mill_sec() - start_time; }
  void set_time_limit(double limit){time_limit = limit;}
  bool is_time_limit_exceeded(){return get_duration() > time_limit;}
private:
  double start_time;
  double time_limit;
  double get_mill_sec() {
    struct timeval res;
    gettimeofday(&res, NULL);
    return res.tv_sec * 1000 + res.tv_usec / 1000;
  }
} timer;
struct Car{
  int idx;
  pii src;
  pii goal;
  Car(){}
  Car(int idx, pii src, pii goal):idx(idx),src(src),goal(goal){}
  bool operator < (const Car &right) const {
    int cost1 = abs(src.first - goal.first) + (src.second - goal.second);
    int cost2 = abs(right.src.first - right.goal.first) + (right.src.second - right.goal.second);
    if (cost1 != cost2){
      return cost1 < cost2;
    }
    return idx < right.idx;
  }
};
bool is_out(int y, int x){
  if (y < 0 or y >= MAX_HW or x < 0 or x >= MAX_HW){
    return true;
  }
  return false;
}
vector<Car> input(){
  vector<Car> cars;
  int H,W,K,T;
  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--;
    cars.emplace_back(Car(i, mp(A,B), mp(C, D)));
  }
  return cars;
}

struct State{
  vector<Car> cars;
  double score;
  shared_ptr<State> parent;
  bitset<900> visited;//30 x 30
  State(){
  }
  // State(const State& state):cars(state.cars),score(state.score),visited(state.visited){
  //   this->parent = NULL;
  // }
  bool operator < (const State &right) const {
    return score < right.score;
  }
};


double calc_score(const vector<Car> &cars, int L){
  double score = 1e7;
  int PD = 20;
  int PL = 10 + 0.01 * L;
  for (const Car &car : cars){
    int diff_y = abs(car.src.first - car.goal.first);
    int diff_x = abs(car.src.second - car.goal.second);
    PD += diff_x + diff_y;
  }
  return score / (PD * PL);
}
void simulate_next_state(const State &state, priority_queue<State> &beams, int L){
  State next_state(state);
  next_state.parent = make_shared<State>(state);
  vector<Car>& cars = next_state.cars;
  for (Car &car : cars){
    int next_dir = rnd.next() % 5;
    int y = car.src.first;
    int x = car.src.second;
    int ny = y + dy[next_dir];
    int nx = x + dx[next_dir];
    if (is_out(ny, nx))continue;
    if (next_state.visited[ny * MAX_HW + nx]){
      continue;
    }
    next_state.visited[ny * MAX_HW + nx] = true;
    car.src = mp(ny, nx);
    // car.src.first = ny;
    // car.src.second = nx;
  }
  next_state.visited.reset();
  for (const Car &car : cars){
    int y,x;
    y = car.src.first;
    x = car.src.second;
    next_state.visited[y * MAX_HW + x] = true;
  }
  next_state.score = calc_score(next_state.cars, L);
  beams.emplace(next_state);
}

vector<string> restore_path(const State &state){
  vector<string> results;
  vector<vector<pii>> paths;
  /////////////////////////////////
  vector<pii> p;
  for (int i = 0; i < state.cars.size(); i++){
    p.emplace_back(state.cars[i].src);
  }
  paths.emplace_back(p);
  //////////////////////////////////
  for (const State *pos = &state;; pos = pos->parent.get()){
    if (pos == NULL){
      break;
    }
    const vector<Car>& cars = pos->cars;
    vector<pii> path;
    for (const Car &car : cars){
      path.emplace_back(car.src);
    }
    paths.push_back(move(path));
  }
  reverse(paths.begin(), paths.end());
  // cout << paths.size() << endl;
  for (int i = 0; i < paths.size() - 1; i++){
    string command = "";
    for (int j = 0; j < paths[i].size(); j++){
      pii pos = paths[i][j];
      pii goal = paths[i + 1][j];
      // cout << pos.first << " " << pos.second << endl;
      // cout << goal.first << " " << goal.second << endl;
      // // cout << endl;
      // assert(pos == goal);
      for (int k = 0; k < 5; k++){
        int y = pos.first + dy[k];
        int x = pos.second + dx[k];
        if (y == goal.first and x == goal.second){
          command += DIRS[k];
          break;
        }
      }
    }
    results.emplace_back(command);
  }
  return results;
}
void output_command(const vector<string> &commands){
  cout << commands.size() << endl;
  for (const string &command : commands){
    cout << command << endl;
  }
}
void solve(vector<Car> cars, int limit){
  State root;
  root.cars = cars;
  for (Car &car : cars){
    int y,x;
    y = car.src.first;
    x = car.src.second;
    root.visited[y * MAX_HW + x] = true;
  }
  State best_state = root;
  double best_score = calc_score(root.cars, 0);
  root.score = best_score;
  priority_queue<State> beams[2];
  beams[0].emplace(root);
  timer.start();
  int cho_iter = 0;
  while (timer.get_duration() < 2000){
    for (int depth = 0; depth < 1500; depth++){
      int cur_depth = depth % 2;
      int next_depth = (depth + 1) % 2;
      for (int iter = 0; iter < 5 and (not beams[cur_depth].empty()); iter++){
        State state = beams[cur_depth].top();
        if (best_score < state.score){
          best_score = state.score;
          best_state = state;
          // cout << calc_score(best_state.cars, depth) << " " << best_score << " " << depth << endl;
          // output_command(restore_path(best_state));
        }
        beams[cur_depth].pop();
        for (int j = 0; j < 20; j++){
          simulate_next_state(state, beams[next_depth], depth + 1);
        }
      }
      while (not beams[cur_depth].empty())beams[cur_depth].pop();
    }
    cho_iter++;
    break;
  }

  vector<string> commands = restore_path(best_state);

  output_command(commands);
  cerr << best_score << endl;
}
int main() {
  vector<Car> cars = input();
  solve(cars, 114514);

  return 0;
}

Submission Info

Submission Time
Task B - 日本橋大渋滞
User togatoga
Language C++14 (GCC 5.4.1)
Score 5518
Code Size 7480 Byte
Status AC
Exec Time 1287 ms
Memory 24288 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 186 / 50000 199 / 50000 196 / 50000 206 / 50000 193 / 50000 194 / 50000 157 / 50000 183 / 50000 182 / 50000 178 / 50000 185 / 50000 189 / 50000 177 / 50000 195 / 50000 195 / 50000 190 / 50000 187 / 50000 176 / 50000 171 / 50000 180 / 50000 175 / 50000 181 / 50000 180 / 50000 174 / 50000 180 / 50000 175 / 50000 200 / 50000 166 / 50000 179 / 50000 189 / 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 1274 ms 22224 KB
subtask_01_02.txt AC 1283 ms 22144 KB
subtask_01_03.txt AC 1280 ms 21768 KB
subtask_01_04.txt AC 1280 ms 22772 KB
subtask_01_05.txt AC 1276 ms 22224 KB
subtask_01_06.txt AC 1276 ms 22624 KB
subtask_01_07.txt AC 1265 ms 23284 KB
subtask_01_08.txt AC 1276 ms 23132 KB
subtask_01_09.txt AC 1277 ms 23284 KB
subtask_01_10.txt AC 1271 ms 23220 KB
subtask_01_11.txt AC 1278 ms 23124 KB
subtask_01_12.txt AC 1278 ms 23136 KB
subtask_01_13.txt AC 1273 ms 22272 KB
subtask_01_14.txt AC 1280 ms 22108 KB
subtask_01_15.txt AC 1277 ms 23188 KB
subtask_01_16.txt AC 1275 ms 22752 KB
subtask_01_17.txt AC 1274 ms 22744 KB
subtask_01_18.txt AC 1268 ms 22160 KB
subtask_01_19.txt AC 1269 ms 23212 KB
subtask_01_20.txt AC 1275 ms 23188 KB
subtask_01_21.txt AC 1271 ms 23152 KB
subtask_01_22.txt AC 1272 ms 22784 KB
subtask_01_23.txt AC 1272 ms 22168 KB
subtask_01_24.txt AC 1269 ms 22724 KB
subtask_01_25.txt AC 1276 ms 23284 KB
subtask_01_26.txt AC 1275 ms 23032 KB
subtask_01_27.txt AC 1287 ms 24288 KB
subtask_01_28.txt AC 1266 ms 23228 KB
subtask_01_29.txt AC 1270 ms 23272 KB
subtask_01_30.txt AC 1282 ms 23276 KB