Submission #1173614

---

Source Code Expand

#include <bits/stdc++.h>

struct Timer {
  Timer() {
    total = 0;
    begintime = rdtsc();
  }
  uint64_t rdtsc() {
    uint64_t u, l;
    __asm__ volatile ("rdtsc" : "=a" (l), "=d" (u)); return ((u << 32) | l);
  }
  void stop() {
    total += (rdtsc() - begintime);
    begintime = 0;
  }
  void start() {
    begintime = rdtsc();
  }
#ifdef LOCAL_
  uint64_t CPS = 2600000000;
  double timelimit = 4;
#else
  uint64_t CPS = 2800000000;
  double timelimit = 4;
#endif
  uint64_t begintime;
  uint64_t total;
  inline double getTime() {
    uint64_t now = rdtsc();
    if( begintime == 0 ) {
      return (double)(total) / CPS;
    }
    return (double)(now - begintime + total) / CPS;
  }
} timer;

#ifndef LOCAL_
#define fprintf if( false ) fprintf
#endif // LOCAL_
#define dumpl(x1) fprintf(stderr, "#%s.%d (%s) = (%ld)\n", __func__, __LINE__, #x1, x1);
#define dumpll(x1, x2) fprintf(stderr, "#%s.%d (%s, %s) = (%ld, %ld)\n", __func__, __LINE__, #x1, #x2, x1, x2);
#define dumpd(x1) fprintf(stderr, "#%s.%d (%s) = (%lf)\n", __func__, __LINE__, #x1, x1);
#define dumpdd(x1, x2) fprintf(stderr, "#%s.%d (%s, %s) = (%lf, %lf)\n", __func__, __LINE__, #x1, #x2, x1, x2);
#define loop for(;;)
 
struct S002 {
  int n;
  S002& operator > (long& x) {
    n = x;
    return *this;
  }
  S002& operator > (long&& x) {
    n = x;
    return *this;
  }
  S002& operator >= (long& x) {
    if( scanf("%ld", &x) <= 0 ) exit(0);
    return *this;
  }
  S002& operator >= (double& x) {
    if( scanf("%lf", &x) <= 0 ) exit(0);
    return *this;
  }
  S002& operator >= (std::string& s) {
    if( not (std::cin >> s) ) exit(0);
    return *this;
  }
  template<typename a>
  S002& operator >= (std::vector<a>& v) {
    v.resize(n);
    for(long i = 0; i < n; ++i) {
      *this >= v[i];
    }
    return *this;
  }
  template<typename a, std::size_t s>
  S002& operator >= (std::array<a, s>& x) {
    for(long i = 0; i < (long)s; ++i) {
      *this >= x[i];
    }
    return *this;
  }
};

struct Point {
  long r, c;
  Point() : r(-1), c(-1) {}
  Point(long r_, long c_) : r(r_), c(c_) {}
  long encode() {
    return r * 32 + c;
  }
  bool inrange() {
    return 1 <= r and r <= 30 and 1 <= c and c <= 30;
  }
};
Point operator + (const Point& x, const Point& y) {
  return Point(x.r + y.r, x.c + y.c);
}
bool operator == (const Point& x, const Point& y) {
  return x.r == y.r and x.c == y.c;
}
Point d4[] = {
  Point(0, 1),
  Point(0, -1),
  Point(1, 0),
  Point(-1, 0)
};
const char cs[] = "RLDU";

struct Car {
  Point src, dest;
  Car() {}
  Car(Point s, Point d) : src(s), dest(d) {}
  long eval() {
    return std::abs(src.r - dest.r) + std::abs(src.c - dest.c) + 20;
  }
  Car move(long i) {
    return Car(src + d4[i], dest);
  }
};

struct Solver {
  long h, w, k, t;
  std::array<Car, 450> cars;
  std::array<long, 1024> field;
  Solver() {
    S002 reader;
    reader >= h >= w >= k >= t;
    std::array<long, 4> ts;
    for(long i = 0; i < k; ++i) {
      reader >= ts;
      cars[i] = Car(Point(ts[0], ts[1]), Point(ts[2], ts[3]));
    }
    genField();
  }
  void genField() {
    for(long& f : field) {
      f = -1;
    }
    for(long i = 0; i < k; ++i) {
      field[cars[i].src.encode()] = i;
    }
  }
  std::vector<std::string> answers;
  bool sub() {
    genField();
    std::array<bool, 32*32> reserved;
    std::string ans;
    bool updated = false;
    for(Car& car : cars) {
      for(long k = 0; k < 4; ++k) {
        Car next = car.move(k);
        if( not reserved[next.src.encode()] and
            field[next.src.encode()] == -1 and 
            car.move(k).eval() < car.eval() ) {
          ans.push_back(cs[k]);
          car = car.move(k);
          reserved[next.src.encode()] = true;
          updated = true;
          goto label_1;
        }
      }
      ans.push_back('-');
    label_1:;
    }
    if( updated ) {
      answers.push_back(ans);
      return true;
    }
    return false;
  }
  void solve() {
    while( sub() ) ;
    writeAnswer();
  }
  void writeAnswer() {
    printf("%ld\n", (long)answers.size());
    for(std::string& s : answers) {
      printf("%s\n", s.c_str());
    }
  }
  
};


// struct Solver {
//   long h, w, k, t;
//   std::array<Point, 450> ss;
//   std::array<Point, 450> ds;
//   std::array<long, 1024> field;
//   Solver() {
//     S002 reader;
//     reader >= h >= w >= k >= t;
//     std::array<long, 4> ts;
//     for(long& f : field) {
//       f = -1;
//     }
//     for(long i = 0; i < k; ++i) {
//       reader >= ts;
//       ss[i] = Point(ts[0], ts[1]);
//       ds[i] = Point(ts[2], ts[3]);
//       field[ss[i].encode()] = i;
//     }
//   }
//   bool shift1() {
//     if( (long)answers.size() >= t ) return false;
//     std::array<char, 451> ans;
//     bool ok = false;
//     std::array<long, 1024> field2 = field;
//     for(long i = 0; i < k; ++i) {
//       if( (ss[i] + d4[3]).inrange() and field[(ss[i] + d4[3]).encode()] == -1 ) {
//         ok = true;
//         field2[(ss[i] + d4[3]).encode()] = i;
//         field2[ss[i].encode()] = -1;
//         ans[i] = cs[3];
//         ss[i] = ss[i] + d4[3];
//       }
//       else {
//         ans[i] = '-';
//       }
//     }
//     ans[450] = '\0';
//     if( ok ) {
//       answers.push_back(&ans[0]);
//       field = field2;
//       return true;
//     }
//     return false;
//   }
//   void reach1() {
//     std::set<long> reserve[1024];
//     for(long i = 0; i < k; ++i) {
//       std::queue<long> q;
//     }
    
//   }
//   void solve() {
//     while( shift1() ) ;
//     while( reach1() ) ;
//     writeAnswer();
//   }
//   void writeAnswer() {
//     printf("%ld\n", (long)answers.size());
//     for(std::string& s : answers) {
//       printf("%s\n", s.c_str());
//     }
//   }
      
// };
 
int main() {
  std::unique_ptr<Solver>(new Solver())->solve();
  return 0;
}

Submission Info

Judge Result