RCO presents 日本橋ハーフマラソン 本戦 (オープン)

Submission #1176027

Source codeソースコード

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <functional>
#include <set>
#include <ctime>
#include <random>
#include <chrono>
#include <cassert>
#include <tuple>
#include <utility>
using namespace std;

namespace {
  using Integer = long long; //__int128;
  template<class T, class S> istream& operator >> (istream& is, pair<T,S>& p){return is >> p.first >> p.second;}
  template<class T> istream& operator >> (istream& is, vector<T>& vec){for(T& val: vec) is >> val; return is;}
  template<class T> istream& operator ,  (istream& is, T& val){ return is >> val;}
  template<class T, class S> ostream& operator << (ostream& os, const pair<T,S>& p){return os << p.first << " " << p.second;}
  template<class T> ostream& operator << (ostream& os, const vector<T>& vec){for(size_t i=0; i<vec.size(); i++) os << vec[i] << (i==vec.size()-1?"":" "); return os;}
  template<class T> ostream& operator ,  (ostream& os, const T& val){ return os << " " << val;}

  template<class H> void print(const H& head){ cout << head; }
  template<class H, class ... T> void print(const H& head, const T& ... tail){ cout << head << " "; print(tail...); }
  template<class ... T> void println(const T& ... values){ print(values...); cout << endl; }

  template<class H> void eprint(const H& head){ cerr << head; }
  template<class H, class ... T> void eprint(const H& head, const T& ... tail){ cerr << head << " "; eprint(tail...); }
  template<class ... T> void eprintln(const T& ... values){ eprint(values...); cerr << endl; }

  class range{ Integer start_, end_, step_; public: struct range_iterator{ Integer val, step_; range_iterator(Integer v, Integer step) : val(v), step_(step) {} Integer operator * (){return val;} void operator ++ (){val += step_;} bool operator != (range_iterator& x){return step_ > 0 ? val < x.val : val > x.val;} }; range(Integer len) : start_(0), end_(len), step_(1) {} range(Integer start, Integer end) : start_(start), end_(end), step_(1) {} range(Integer start, Integer end, Integer step) : start_(start), end_(end), step_(step) {} range_iterator begin(){ return range_iterator(start_, step_); } range_iterator   end(){ return range_iterator(  end_, step_); } };

  inline string operator "" _s (const char* str, size_t size){ return move(string(str)); }
  constexpr Integer my_pow(Integer x, Integer k, Integer z=1){return k==0 ? z : k==1 ? z*x : (k&1) ? my_pow(x*x,k>>1,z*x) : my_pow(x*x,k>>1,z);}
  constexpr Integer my_pow_mod(Integer x, Integer k, Integer M, Integer z=1){return k==0 ? z%M : k==1 ? z*x%M : (k&1) ? my_pow_mod(x*x%M,k>>1,M,z*x%M) : my_pow_mod(x*x%M,k>>1,M,z);}
  constexpr unsigned long long operator "" _ten (unsigned long long value){ return my_pow(10,value); }

  inline int k_bit(Integer x, int k){return (x>>k)&1;} //0-indexed


  template<class T> string join(const vector<T>& v, const string& sep){ stringstream ss; for(size_t i=0; i<v.size(); i++){ if(i>0) ss << sep; ss << v[i]; } return ss.str(); }

  inline string operator * (string s, int k){ string ret; while(k){ if(k&1) ret += s; s += s; k >>= 1; } return ret; }
}
constexpr long long mod = 9_ten + 7;

class XorShift{
public:
  uint32_t x;
  uint32_t y;
  uint32_t z;
  uint32_t w;

  XorShift(){
    x = 123456789;
    y = 362436069;
    z = 521288629;
    w = 88675123;
  }
  
  XorShift(uint32_t seed){
    x = 123456789;
    y = 362436069;
    z = 521288629;
    w = seed;

    for(int i=0; i<100; i++){
      (*this)();
    }
  }
  
  uint32_t operator () () {
    uint32_t t = x ^ (x << 11);
    
    x = y; y = z; z = w;
    return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); 
  }
};

template<class T>
class Min_Cost_Flow{
public:

  struct edge{
    int to;
    int cap;
    T cost;
    int rev;
    bool is_rev;
  };

  const T INF;
  vector<vector<edge>> G;

  Min_Cost_Flow(int n, T inf) : G(n), INF(inf){

  }

  void add_edge(int from, int to, int cap, T cost){
    G[from].push_back((edge){to, cap, cost, (int)G[to].size(), false});
    G[to].push_back((edge){from, 0, -cost, (int)G[from].size()-1, true});
  }


  //min cost : s->t (flow:f)
  T min_cost_flow(int s, int t, int f){
    const int N = G.size();
    T cost = 0;
    vector<int> prev_v(N,-1);
    vector<int> prev_e(N,-1);
    vector<T> potantial(N, 0);

    
    while(f>0){
      //min distance(cost based) search with SPFA
      vector<T> dist(N, INF);
      
      vector<int> cnt(dist.size(), 0);
      dist[s] = 0;
      prev_v[s] = s;

      queue<int> Q;
      auto my_push = [&](int node){
        Q.push(node);
        cnt[node]++;
      };
      auto my_pop = [&]() -> int{
        int ret = Q.front();
        cnt[ret]--;
        Q.pop();
        return ret;
      };
      my_push(s);
      while(!Q.empty()){
        int pos = my_pop();
        for(int i=0; i<G[pos].size(); i++){
          edge& E = G[pos][i];
          T new_dist = dist[pos] + E.cost + potantial[E.to] - potantial[pos];
          if(dist[E.to] > new_dist && E.cap > 0){
            dist[E.to] = new_dist;
            prev_v[ E.to ] = pos;
            prev_e[ E.to ] = i;

            if(cnt[ E.to ] == 0){
              my_push( E.to );
            }
          }
        }
      }
      for(int i=0; i<N; i++){
        dist[i] = potantial[i] + dist[i];
      }

      //cannot achieved to "t" return -1
      if(dist[t]>=INF) return -1;

      //add cost of s->t with flow=d
      int pos=t;
      int d=f;
      while(pos!=s){
        int i=prev_v[pos];
        int j=prev_e[pos];
        pos = i;
        d = min(d, G[i][j].cap);
      }
      
      pos = t;
      //cout << t ;
      while(pos!=s){
        int i=prev_v[pos];
        int j=prev_e[pos];
        G[i][j].cap -= d;
        G[ G[i][j].to ][ G[i][j].rev ].cap += d;
        //cost += G[i][j].cost * d;
        pos = i;
        //cout << " <- " << pos;
      }
      //cout << endl;
      cost += d * dist[t];
      f -= d;

      //f==0 then end
    }
    return cost;
  }
};



constexpr int H = 30, W = 30;
constexpr int K = 450;
//constexpr int T=50;
/**
* パラメータ
*/
constexpr int T = 200;
constexpr int BeamWidth = 10;
constexpr int BeamNext = 2;
constexpr unsigned long long seed_mt = 1145148931919ll;
constexpr unsigned int seed_xor = 1919893;
mt19937_64 mt(seed_mt);
XorShift xrand(seed_xor);

constexpr int mask = 1<<20;
constexpr int threshold_move_good = mask * 0.95;
constexpr int threshold_move_bad = mask * 0.05;

long long calc_score( vector<pair<int,int>>& pos, vector<pair<int,int>>& target ){
  long long ret = 0;
  for(int i=0; i<pos.size(); i++){
    ret += abs( pos[i].first - target[i].first ) + abs( pos[i].second - target[i].second );
  }
  return ret;
}

struct state{
  vector<pair<int,int>> p;
  long long score;
  string move;
};

int dx[] = {0, 0, 1,-1};
int dy[] = {1,-1, 0, 0};
char dc[] = {'D','U','R','L'};

vector<string> gen_next_state(vector<pair<int,int>>& now, vector<pair<int,int>>& target){
  vector<string> res(2, string(now.size(), '-'));

  vector<pair<int,int>> s = now;

  vector<vector<int>> cell(H, vector<int>(W, -1));
  for(int i=0; i<s.size(); i++){
    int r,c;
    tie(r,c) = s[i];
    cell[r][c] = i;
  }

  vector<vector<bool>> used_cell(H, vector<bool>(W, false));

  vector<int> value(now.size(), 0);
  for(int i=0; i<s.size(); i++){
    //value[i] += abs(target[i].first - 15) + abs(target[i].second - 15);
    int tmp = abs(target[i].first - now[i].second) + abs(target[i].second - now[i].second);
    value[i] += tmp*tmp;
    value[i] += xrand()&15;
  }

  vector<int> order(now.size());
  iota(order.begin(), order.end(), 0);
  if( (xrand()&255) < 70){
    shuffle(order.begin(), order.end(), mt);
  }else{
    sort(order.begin(), order.end(), [&](int l, int r){
      return value[l] > value[r];
    });
    //shuffle(order.begin(), order.begin()+70, mt);
  }

  auto get_cost = [&](int id, int y, int x){
    return abs( y - target[id].first ) + abs( x - target[id].second );
  };

  auto get_rotate_cost = [&](int ay, int ax, int by, int bx){
    const int inf = 114514893;
    if(ay<0 || ay>=H || ax<0 || ax>=W) return inf;
    if(by<0 || by>=H || bx<0 || bx>=W) return inf;

    for(int y=min(ay,by); y<=max(ay,by); y++) for(int x=min(ax,bx); x<=max(ax,bx); x++){
      if( used_cell[y][x] == true ) return inf;
    }
    int u = cell[ay][ax];
    int v = cell[by][bx];

    return (get_cost( u, by,bx ) - get_cost( u, ay,ax )) + 
           (get_cost( v, ay,ax ) - get_cost( v, by,bx )) ;
  };


  vector<string> dir = {
    "RD","DL","UR","LU"
  };
  auto rotate = [&](int ay, int ax, int by, int bx){
    int i = 0;
    int u = cell[ay][ax];
    int v = cell[by][bx];
    for(int y=min(ay,by); y<=max(ay,by); y++) for(int x=min(ax,bx); x<=max(ax,bx); x++){
      if( y==ay && x==ax ){
        res[0][ u ] = dir[i][0];
        res[1][ u ] = dir[i][1];
      }else if( y==by && x==bx ){
        res[0][ v ] = dir[i][0];
        res[1][ v ] = dir[i][1];
      }
      i++;
      used_cell[y][x] = true;
    }
    swap(s[ u ], s[ v ]);
  };


  for(int i : order){
    if(used_cell[ now[i].first ][ now[i].second ]) continue;
    int dy = target[i].first - now[i].first;
    int dx = target[i].second - now[i].second;
    if(dx == 0 && dy == 0) continue;

    int r = now[i].first;
    int c = now[i].second;

    bool updated = false;
    vector< tuple<int,int,int> > rot;
    for(int yy=-1; yy<=1; yy+=2) for(int xx=-1; xx<=1; xx+=2){
      auto cost = get_rotate_cost(r,c, r+yy,c+xx);

      if( cost >= 4 ) continue;

      rot.emplace_back( cost, r+yy, c+xx );
    }
    if(rot.size() == 0 || updated) continue;

    shuffle(rot.begin(), rot.end(), mt);

    if((xrand()&511) < 500) for(auto& rr : rot){
      if( get<0>(rr) < -2 ){
        rotate( r,c, get<1>(rr), get<2>(rr) );
        updated = true;
        break;
      }
    }

    if( (xrand()&255) < 200 ){


      if( !updated && abs(dx) > abs(dy) ){
        for(auto& rr : rot){
          if( (get<2>(rr)<c) != (dx<0) ) continue;
          rotate( r,c, get<1>(rr), get<2>(rr) );
          updated = true;
          break;
        }
      }
      if( !updated && abs(dx) < abs(dy)){
        for(auto& rr : rot){
          if( (get<1>(rr)<r) != (dy<0) ) continue;
          rotate( r,c, get<1>(rr), get<2>(rr) );
          updated = true;
          break;
        }
      }

    }else{
      if( !updated && abs(dx) < abs(dy)){
        for(auto& rr : rot){
          if( (get<1>(rr)<r) != (dy<0) ) continue;
          rotate( r,c, get<1>(rr), get<2>(rr) );
          updated = true;
          break;
        }
      }

      if( !updated && abs(dx) > abs(dy) ){
        for(auto& rr : rot){
          if( (get<2>(rr)<c) != (dx<0) ) continue;
          rotate( r,c, get<1>(rr), get<2>(rr) );
          updated = true;
          break;
        }
      }

    }


  }

  now = s;
  return res;
}

vector<string> gen_unko_state(vector<pair<int,int>>& now, vector<pair<int,int>>& target){
  vector<string> res(2, string(now.size(), '-'));

  vector<pair<int,int>> s = now;

  vector<vector<int>> cell(H, vector<int>(W, -1));
  for(int i=0; i<s.size(); i++){
    int r,c;
    tie(r,c) = s[i];
    cell[r][c] = i;
  }

  vector<vector<bool>> used_cell(H, vector<bool>(W, false));

  vector<int> order(now.size());
  iota(order.begin(), order.end(), 0);
  shuffle(order.begin(), order.end(), mt);

  auto get_cost = [&](int id, int y, int x){
    return abs( y - target[id].first ) + abs( x - target[id].second );
  };

  auto get_rotate_cost = [&](int ay, int ax, int by, int bx){
    const int inf = 114514893;
    if(ay<0 || ay>=H || ax<0 || ax>=W) return inf;
    if(by<0 || by>=H || bx<0 || bx>=W) return inf;

    for(int y=min(ay,by); y<=max(ay,by); y++) for(int x=min(ax,bx); x<=max(ax,bx); x++){
      if( used_cell[y][x] == true ) return inf;
    }
    int u = cell[ay][ax];
    int v = cell[by][bx];

    return (get_cost( u, by,bx ) - get_cost( u, ay,ax )) + 
           (get_cost( v, ay,ax ) - get_cost( v, by,bx )) ;
  };


  vector<string> dir = {
    "RD","DL","UR","LU"
  };
  auto rotate = [&](int ay, int ax, int by, int bx){
    int i = 0;
    int u = cell[ay][ax];
    int v = cell[by][bx];
    for(int y=min(ay,by); y<=max(ay,by); y++) for(int x=min(ax,bx); x<=max(ax,bx); x++){
      if( y==ay && x==ax ){
        res[0][ u ] = dir[i][0];
        res[1][ u ] = dir[i][1];
      }else if( y==by && x==bx ){
        res[0][ v ] = dir[i][0];
        res[1][ v ] = dir[i][1];
      }
      i++;
      used_cell[y][x] = true;
    }
    swap(s[ u ], s[ v ]);
  };


  for(int i : order){
    if(used_cell[ now[i].first ][ now[i].second ]) continue;
    int dy = target[i].first - now[i].first;
    int dx = target[i].second - now[i].second;
    if(dx == 0 && dy == 0) continue;

    int r = now[i].first;
    int c = now[i].second;

    bool updated = false;
    vector< tuple<int,int,int> > rot;
    for(int yy=-1; yy<=1; yy+=2) for(int xx=-1; xx<=1; xx+=2){
      auto cost = get_rotate_cost(r,c, r+yy,c+xx);

      if( cost > 4 ) continue;

      rot.emplace_back( cost, r+yy, c+xx );
    }
    if(rot.size() == 0 || updated) continue;

    shuffle(rot.begin(), rot.end(), mt);

    if((xrand()&255) < 200) for(auto& rr : rot){
      if( get<0>(rr) < 4 ){
        rotate( r,c, get<1>(rr), get<2>(rr) );
        updated = true;
        break;
      }
    }
  }

  now = s;
  return res;
}

long long calc_actual_score(int L, vector<pair<int,int>>& s, vector<pair<int,int>>& t){
  long long pd = 20 + calc_score(s,t);
  double pt = 10 + L * 0.01;

  return ceil( 1e7 / (pd*pt) );
}


vector<string> adjust_state(vector<pair<int,int>>& p, vector<pair<int,int>>& target){
  vector<string> res;
  int k = p.size();
  vector<int> order(k);
  iota(order.begin(), order.end(), 0);
  vector<int> order_r(H);
  iota(order_r.begin(), order_r.end(), 0);
  vector<int> order_c(W);
  iota(order_c.begin(), order_c.end(), 0);
  vector<int> order_j(4);
  iota(order_j.begin(), order_j.end(), 0);

  for(int t : range(2)){
    int source = H*W + 0;
    int sink   = H*W + 1;
    Min_Cost_Flow<int> f(H*W + 2, 1e8);

    vector<vector<int>> cell(H, vector<int>(W, -1));

    shuffle(order.begin(), order.end(), mt);
    shuffle(order_c.begin(), order_c.end(), mt);
    shuffle(order_r.begin(), order_r.end(), mt);

    for(int i : order){
      int r,c;
      tie(r,c) = p[i];
      cell[r][c] = i;
      f.add_edge( source, r*W+c, 1, 0 );
    }

    for(int r : order_r){
      for(int c : order_c){
        if(cell[r][c] != -1){
          shuffle(order_j.begin(), order_j.end(), mt);

          for(int j : order_j){
            int rr = r + dy[j];
            int cc = c + dx[j];
            if( rr<0 || rr>=H || cc<0 || cc>=W ) continue;

            int i = cell[r][c];
            int score_prev = abs( r - target[i].first ) + abs( c - target[i].second );
            int score_next = abs( rr - target[i].first ) + abs( cc - target[i].second );
            f.add_edge( r*W + c, rr*W + cc, 1000, score_next - score_prev );
          }

        }else{
          f.add_edge(r*W+c, sink, 1, 0);
        }

      }
    }


    int cost = f.min_cost_flow(source, sink, k);
    if(cost == 0) break;

    string moving_(k, '-');
    auto next_cell = cell;

    for(int r=0; r<H; r++){
      for(int c=0; c<W; c++){
        int pos = r*W+c;
        if(cell[r][c] < 0) continue;
        for(auto e : f.G[pos] ){
          if( e.to == source || e.to == sink) continue;
          if( e.is_rev ) continue;
          if( e.cap == 1000 ) continue;
          int rr = e.to/W;
          int cc = e.to%W;

          if(cell[rr][cc] != -1) continue;
          cell[rr][cc] = -2;

          char m = '-';

          if(rr<r) m = 'U';
          if(rr>r) m = 'D';

          if(cc<c) m = 'L';
          if(cc>c) m = 'R';

          moving_[ cell[r][c] ] = m;

          p[ cell[r][c] ] = {rr,cc};
          break;
        }
      }
    }

    res.push_back( moving_ );

  }

  return res;
}


tuple<vector<pair<int,int>>, vector<string>> move_to_ichimatsu(vector<pair<int,int>> p){
  vector<string> res;
  int k = p.size();
  while(true){
    int source = H*W + 0;
    int sink   = H*W + 1;
    Min_Cost_Flow<int> f(H*W + 2, 1e8);

    vector<vector<int>> cell(H, vector<int>(W, -1));
    for(int i=0; i<k; i++){
      int r,c;
      tie(r,c) = p[i];
      cell[r][c] = i;
      f.add_edge( source, r*W+c, 1, 0 );
    }

    for(int r=0; r<H; r++){
      for(int c=0; c<W; c++){
        for(int j=0; j<4; j++){
          int rr = r + dy[j];
          int cc = c + dx[j];
          if( rr<0 || rr>=H || cc<0 || cc>=W ) continue;
          f.add_edge( r*W + c, rr*W + cc, 1000, 1);
        }

        if( ((r+c)&1) == 0 ){
          f.add_edge(r*W+c, sink, 1, 0);
        }
      }
    }


    int cost = f.min_cost_flow(source, sink, k);
    if(cost == 0) break;

    string moving_(k, '-');
    auto next_cell = cell;

    for(int r=0; r<H; r++){
      for(int c=0; c<W; c++){
        int pos = r*W+c;
        if(cell[r][c] < 0) continue;
        for(auto e : f.G[pos] ){
          if( e.to == source || e.to == sink) continue;
          if( e.is_rev ) continue;
          if( e.cap == 1000 ) continue;
          int rr = e.to/W;
          int cc = e.to%W;

          if(cell[rr][cc] != -1) continue;
          cell[rr][cc] = -2;

          char m = '-';

          if(rr<r) m = 'U';
          if(rr>r) m = 'D';

          if(cc<c) m = 'L';
          if(cc>c) m = 'R';

          moving_[ cell[r][c] ] = m;

          p[ cell[r][c] ] = {rr,cc};
          break;
        }
      }
    }

    res.push_back( moving_ );

  }

  return make_tuple(p, res);
}

vector<pair<int,int>> get_prev(vector<pair<int,int>> s, string& moving){
  for(int i=0; i<moving.size(); i++){
    if( moving[i] == 'U' ) s[i].first++;
    else if( moving[i] == 'D' ) s[i].first--;
    else if( moving[i] == 'R' ) s[i].second--;
    else if( moving[i] == 'L' ) s[i].second++;
  }
  return s;
}

#include <unordered_set>

int main(){
  auto start_time = chrono::steady_clock::now();

  int h,w,k,t;
  cin >> h,w,k,t;


  vector<vector<unsigned long long>> zobrist_hash(k, vector<unsigned long long>(h*w, 0));
  for(int i=0; i<k; i++){
    for(int r=0; r<H; r++){
      for(int c=0; c<W; c++){
        zobrist_hash[i][r*W+c] = mt();
      }
    }
  }


  vector<pair<int,int>> a(k),target(k);
  for(auto i : range(k) ){
    int ra, ca;
    cin >> ra, ca;
    a[i] = {ra-1,ca-1};

    int rt, ct;
    cin >> rt, ct;
    target[i] = {rt-1, ct-1};
  }

  //set initial position
  auto state_initial = move_to_ichimatsu(a);
  auto state_after   = move_to_ichimatsu(target);

  auto a_ = get<0>(state_initial);
  auto target_ = get<0>(state_after);

  vector<string> res = get<1>(state_initial);

  unordered_set<unsigned long long> memo;
  auto get_hash = [&](vector<pair<int,int>>& s){
    unsigned long long h = 0;
    for(int i=0; i<k; i++){
      h ^= zobrist_hash[ i ][ s[i].first*W + s[i].second ];
    }
    return h;
  };
  memo.insert( get_hash(a_) );

  bool last_adjust  = false;
  bool last_skipped = false;

  for(int step=0; step<500; step++){
    auto prev_a = a_;
    vector<string> nx;

    int type = 0;
    if((last_adjust && last_skipped) == false &&
       ( ( step<20 && (xrand()&255) < 130 )  || 
       ( step<500 && (xrand()&255) < 160 + (step>>2) ) )
     ){
      nx = adjust_state( a_, target_ );
      type = 0;
    // }else if( step < 50 && (xrand()&255) < 10 ){
    //   nx = gen_unko_state( a_, target_ );
    //   type = 1;
    }else{
      nx = gen_next_state( a_, target_ );
      type = 1;
    }

    last_adjust = type==0;

    // auto h = get_hash( a_ );
    // if(memo.count(h)){
    //   a_ = prev_a;
    //   last_skipped = true;
    //   continue;
    // }

    last_skipped = false;

    // memo.insert(h);

    for(auto s : nx){
      if( count(s.begin(), s.end(), '-') == k ) continue;
      res.push_back( s );
    }

    if(a_ == target_) break;
  }

  while( true ){
    auto last_a_ = a_;
    auto time_now = chrono::steady_clock::now();
    if(chrono::duration_cast<chrono::milliseconds>(time_now - start_time).count() > 3650){
      break;
    }

    int step_back = ((xrand()&7)<<1) + 8;
    for(int i=0; i<step_back; i++){
      a_ = get_prev(a_, res[res.size()-1-i]);
    }
    eprintln("prev : ", res.size());

    vector<string> new_moving;

    int prob_adjust = (xrand()&255);

    for(int step=0; step<(step_back>>1)-1; step++){

    if(chrono::duration_cast<chrono::milliseconds>(time_now - start_time).count() > 3650){
      break;
    }

      auto prev_a = a_;
      vector<string> nx;

      int type = 0;
      if((last_adjust && last_skipped) == false &&
         (xrand()&255) < prob_adjust
       ){
        nx = adjust_state( a_, target_ );
        type = 0;
      }else if(((xrand()&255) < 5 && step<5) ){
        nx = gen_unko_state( a_, target_ );
        type = 1;
      }else{
        nx = gen_next_state( a_, target_ );
        type = 1;
      }

      last_adjust = type==0;

      last_skipped = false;

      for(auto s : nx){
        if( count(s.begin(), s.end(), '-') == k ) continue;
        new_moving.push_back( s );
      }
      if(a_ == target_) break;
    }

    eprintln("next : ", res.size());

    if(a_ == target_ && new_moving.size() < step_back){
      eprintln("update");
      for(int i=0; i<step_back; i++){
        res.pop_back();
      }
      for(auto s: new_moving){
        res.push_back( s );
      }
    }else{
      a_ = last_a_;
    }
  }

  eprintln("break");

  if(a_ == target_){
    vector<string> tmp = get<1>(state_after);
    reverse(tmp.begin(), tmp.end());
    for(auto& moving : tmp){
      for(auto& c : moving){
        if(c == 'U') c = 'D';
        else if(c == 'D') c = 'U';
        else if(c == 'L') c = 'R';
        else if(c == 'R') c = 'L';
      }
      res.push_back(moving);
    }
  }

  println( res.size() );
  println( join(res, "\n") );

  eprintln( res.size() );
  eprintln( calc_actual_score( res.size(), a_, target_) );

  auto end_time = chrono::steady_clock::now();
  eprintln( chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count(), "[ms]" );

  return 0;
}

Submission

Task問題 B - 日本橋大渋滞
User nameユーザ名 koyumeishi
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 1312871
Source lengthソースコード長 22996 Byte
File nameファイル名
Exec time実行時間 3865 ms
Memory usageメモリ使用量 5888 KB

Test case

Set

Set name Score得点 / Max score Cases
test_01 44524 / 50000 subtask_01_01.txt
test_02 43328 / 50000 subtask_01_02.txt
test_03 43669 / 50000 subtask_01_03.txt
test_04 43707 / 50000 subtask_01_04.txt
test_05 44248 / 50000 subtask_01_05.txt
test_06 43517 / 50000 subtask_01_06.txt
test_07 43366 / 50000 subtask_01_07.txt
test_08 43822 / 50000 subtask_01_08.txt
test_09 43479 / 50000 subtask_01_09.txt
test_10 43366 / 50000 subtask_01_10.txt
test_11 43707 / 50000 subtask_01_11.txt
test_12 43976 / 50000 subtask_01_12.txt
test_13 44287 / 50000 subtask_01_13.txt
test_14 43441 / 50000 subtask_01_14.txt
test_15 43216 / 50000 subtask_01_15.txt
test_16 43517 / 50000 subtask_01_16.txt
test_17 43899 / 50000 subtask_01_17.txt
test_18 42956 / 50000 subtask_01_18.txt
test_19 43631 / 50000 subtask_01_19.txt
test_20 44287 / 50000 subtask_01_20.txt
test_21 43937 / 50000 subtask_01_21.txt
test_22 44170 / 50000 subtask_01_22.txt
test_23 44248 / 50000 subtask_01_23.txt
test_24 43669 / 50000 subtask_01_24.txt
test_25 43783 / 50000 subtask_01_25.txt
test_26 43291 / 50000 subtask_01_26.txt
test_27 44092 / 50000 subtask_01_27.txt
test_28 43860 / 50000 subtask_01_28.txt
test_29 43669 / 50000 subtask_01_29.txt
test_30 44209 / 50000 subtask_01_30.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
subtask_01_01.txt AC 3680 ms 3840 KB
subtask_01_02.txt AC 3842 ms 5760 KB
subtask_01_03.txt AC 3680 ms 3840 KB
subtask_01_04.txt AC 3681 ms 3840 KB
subtask_01_05.txt AC 3738 ms 3840 KB
subtask_01_06.txt AC 3666 ms 5760 KB
subtask_01_07.txt AC 3829 ms 3840 KB
subtask_01_08.txt AC 3686 ms 3968 KB
subtask_01_09.txt AC 3739 ms 3840 KB
subtask_01_10.txt AC 3729 ms 3840 KB
subtask_01_11.txt AC 3688 ms 5760 KB
subtask_01_12.txt AC 3771 ms 3840 KB
subtask_01_13.txt AC 3792 ms 3840 KB
subtask_01_14.txt AC 3664 ms 3964 KB
subtask_01_15.txt AC 3698 ms 3968 KB
subtask_01_16.txt AC 3690 ms 3968 KB
subtask_01_17.txt AC 3691 ms 3840 KB
subtask_01_18.txt AC 3865 ms 5888 KB
subtask_01_19.txt AC 3660 ms 3840 KB
subtask_01_20.txt AC 3748 ms 3840 KB
subtask_01_21.txt AC 3673 ms 3840 KB
subtask_01_22.txt AC 3698 ms 3840 KB
subtask_01_23.txt AC 3733 ms 5760 KB
subtask_01_24.txt AC 3683 ms 3968 KB
subtask_01_25.txt AC 3735 ms 3840 KB
subtask_01_26.txt AC 3704 ms 3968 KB
subtask_01_27.txt AC 3696 ms 3840 KB
subtask_01_28.txt AC 3655 ms 3840 KB
subtask_01_29.txt AC 3690 ms 3840 KB
subtask_01_30.txt AC 3678 ms 3840 KB