Submission #1180485


Source Code Expand

#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 unsigned long long seed_mt = 1145148931919ll;
constexpr unsigned int seed_xor = 1919893;
mt19937_64 mt(seed_mt);
XorShift xrand(seed_xor);

int dx[] = {0,0,-1,1};
int dy[] = {1,-1,0,0};

tuple<vector<pair<int,int>>, vector<string>> make_checker(vector<pair<int,int>> s){
  const int inf = 1e8;
  vector<string> res;
  while(true){
    Min_Cost_Flow<int> f(H*W+2, inf);
    int source = H*W;
    int sink   = H*W + 1;


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

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

    for(int r : range(H)) for(int c : range(W)){
      if( ((r+c)&1) == 0 ) f.add_edge( r*W+c, sink, 1, 0 );

      for(int k : range(4)){
        int rr = r + dy[k];
        int cc = c + dx[k];

        if( rr<0 || rr>=H || cc<0 || cc>=W ) continue;
        f.add_edge( r*W+c, rr*W+cc, 1000, 1 );
      }
    }

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


    string movement(K, '-');
    for(int i : range(K)){
      int r,c;
      tie(r,c) = s[i];

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

        if( rr != r ) movement[i] = rr<r ? 'U' : 'D';
        if( cc != c ) movement[i] = cc<c ? 'L' : 'R';

        s[i] = {rr,cc};
        break;
      }
    }

    res.push_back( movement );
  }

  return make_tuple( s, res );
}

vector<string> get_next(vector<pair<int,int>>& s, vector<pair<int,int>>& target){
  const int inf = 1e8;
  vector<string> res;

  vector<int> order_s(K), order_r(H), order_c(W), order_adj(4);
  iota(order_s.begin(), order_s.end(), 0);
  iota(order_r.begin(), order_r.end(), 0);
  iota(order_c.begin(), order_c.end(), 0);
  iota(order_adj.begin(), order_adj.end(), 0);

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

    string movement(K, '-');

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

    shuffle(order_s.begin(), order_s.end(), mt);
    for(int i : order_s){
      int r,c;
      tie(r,c) = s[i];
      f.add_edge( source, r*W+c, 1, 0 );
      cell[r][c] = i;
    }

    shuffle(order_r.begin(), order_r.end(), mt);
    shuffle(order_c.begin(), order_c.end(), mt);
    for(int r : order_r) for(int c : order_c){
      if( cell[r][c] == -1){
        f.add_edge( r*W+c, sink, 1, 0 );
      }else{
        int i = cell[r][c];
        shuffle(order_adj.begin(), order_adj.end(), mt);
        for(int k : order_adj){
          int rr = r + dy[k];
          int cc = c + dx[k];

          if( rr<0 || rr>=H || cc<0 || cc>=W ) continue;
          int prev_score = abs( r - target[i].first ) + abs( c - target[i].second );
          int next_score = abs( rr- target[i].first ) + abs( cc- target[i].second );

          
          f.add_edge( r*W+c, rr*W+cc, 1000, min(1, (next_score-prev_score)*prev_score) );
        }
      }
    }

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

    for(int i : order_s){
      int r,c;
      tie(r,c) = s[i];

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

        if( rr != r ) movement[i] = rr<r ? 'U' : 'D';
        if( cc != c ) movement[i] = cc<c ? 'L' : 'R';

        s[i] = {rr,cc};
        break;
      }
    }

    res.push_back( movement );
  }

  return res;
}


int main(){
  int h_,w_,k_,t_;
  cin >> h_,w_,k_,t_;

  vector<pair<int,int>> initial(K),target(K);
  for(auto i : range(K) ){
    int ri, ci;
    cin >> ri, ci;
    initial[i] = {ri-1, ci-1};

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

  auto initial_checker = make_checker( initial );
  auto target_checker = make_checker( target );

  auto s = get<0>( initial_checker );
  auto t = get<0>( target_checker );


  vector<string> res = get<1>( initial_checker );
  for(int i=0; i<200; i++){
    auto prev = s;
    auto res_ = get_next(s, t);

    if(prev == s){
      //eprintln("same");
      continue;
    }

    for(auto m : res_){
      res.push_back(m);
    }
    if(s == t) break;
  }


  auto res_ = get<1>(target_checker);
  for(auto& m : res_){
    for(auto& c : m){
      if( c == 'U' ) c = 'D';
      else if( c == 'D' ) c = 'U';
      else if( c == 'L' ) c = 'R';
      else if( c == 'R' ) c = 'L';
    }
  }
  reverse(res_.begin(), res_.end());

  if(s == t){
    for(auto& m : res_){
      res.push_back(m);
    }
  }

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

  return 0;
}

Submission Info

Submission Time
Task B - 日本橋大渋滞
User koyumeishi
Language C++14 (GCC 5.4.1)
Score 1330975
Code Size 11284 Byte
Status TLE
Exec Time 4203 ms
Memory 700 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 46254 / 50000 45872 / 50000 45621 / 50000 46383 / 50000 45872 / 50000 45999 / 50000 45999 / 50000 46297 / 50000 45999 / 50000 45373 / 50000 45956 / 50000 46340 / 50000 46083 / 50000 45830 / 50000 45872 / 50000 46254 / 50000 46041 / 50000 45621 / 50000 45704 / 50000 45999 / 50000 46126 / 50000 45788 / 50000 45704 / 50000 45290 / 50000 45788 / 50000 46169 / 50000 0 / 50000 45538 / 50000 45830 / 50000 45373 / 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
TLE × 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 1938 ms 608 KB
subtask_01_02.txt AC 2520 ms 620 KB
subtask_01_03.txt AC 2720 ms 592 KB
subtask_01_04.txt AC 1888 ms 644 KB
subtask_01_05.txt AC 2412 ms 680 KB
subtask_01_06.txt AC 2220 ms 688 KB
subtask_01_07.txt AC 2143 ms 624 KB
subtask_01_08.txt AC 1932 ms 608 KB
subtask_01_09.txt AC 2094 ms 600 KB
subtask_01_10.txt AC 2956 ms 636 KB
subtask_01_11.txt AC 2645 ms 652 KB
subtask_01_12.txt AC 2004 ms 624 KB
subtask_01_13.txt AC 2176 ms 632 KB
subtask_01_14.txt AC 2256 ms 664 KB
subtask_01_15.txt AC 2368 ms 616 KB
subtask_01_16.txt AC 2001 ms 612 KB
subtask_01_17.txt AC 2114 ms 608 KB
subtask_01_18.txt AC 2572 ms 664 KB
subtask_01_19.txt AC 2383 ms 632 KB
subtask_01_20.txt AC 2369 ms 624 KB
subtask_01_21.txt AC 2321 ms 656 KB
subtask_01_22.txt AC 2443 ms 620 KB
subtask_01_23.txt AC 2627 ms 612 KB
subtask_01_24.txt AC 2508 ms 608 KB
subtask_01_25.txt AC 2525 ms 600 KB
subtask_01_26.txt AC 2450 ms 608 KB
subtask_01_27.txt TLE 4203 ms 604 KB
subtask_01_28.txt AC 2622 ms 612 KB
subtask_01_29.txt AC 2198 ms 628 KB
subtask_01_30.txt AC 2483 ms 700 KB