Submission #1174462

---

Source Code Expand

#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <string.h>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <map>
#include <set>
#include <iostream>
#include <sstream>
#include <numeric>
#include <cctype>
#include <bitset>
#include <cassert>
#include <random>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define gep(i,g,j) for(int i = g.head[j]; i != -1; i = g.e[i].next)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcount
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define df(x) int x = in()
#define dame { puts("-1"); return 0;}
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,vector<T>,greater<T> >
#define bn(x) ((1<<x)-1)
#define newline puts("")
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
inline void priv(vi a) { rep(i,sz(a)) printf("%d%c",a[i],i==sz(a)-1?'\n':' ');}
template<typename T>istream& operator>>(istream&i,vector<T>&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(const vector<T>&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>ostream& operator<<(ostream&o,const vector<T>&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>istream& operator>>(istream&i,const pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
const ll LINF = 1e18;
const double eps = 1e-10;
typedef vector<string> vs;
const int di[] = {-1,0,1,0,0}, dj[] = {0,-1,0,1,0}; //^<v>
const string dc = "ULDR-";
const int cost[] = {1,1,1,1};
// const int cost[] = {10,25,50,100};

const int MH = 30, INF = 1001001001;
const int MN = 450;
const int TURN = 200, AD = 1000, ED = 100;
const int MS = 10;

int h, w, n, T;
struct V {
  int i, j;
  V(int i = 0, int j = 0):i(i),j(j){}
  bool operator==(const V& a)const{ return i==a.i&&j==a.j;}
};
struct D {
  int d;
  V v;
  D(int d = 0, V v = V(0,0)):d(d),v(v){}
  bool operator<(const D& a)const{ return d>a.d;}
};
typedef vector<V> vv;
vv s, t;
V inV() {
  int i,j;
  scanf("%d%d",&i,&j);
  return V(i-1,j-1);
}
vvi o;
int& ov(V& v) { return o[v.i][v.j];}
void prii(vvi& data) {
  for (vi nd : data) {
    // for (int md : nd) printf("%d",md);
    // newline;
    cout<<nd<<endl;
  }
}

int vc[MH][MH][5];
void setxv() {
  auto setvc = [&](int nvc[5], int v, int u) {
    nvc[v] = cost[0];
    nvc[u] = cost[1];
    nvc[u^2] = cost[2];
    nvc[v^2] = cost[3];
  };
  rep(x,h/2) {
    int i = x, j = x;
    if (x&1) {
      while (j<w-1-x) {
        setvc(vc[i][j],3,0);
        ++j;
      }
      while (i<h-1-x) {
        setvc(vc[i][j],2,3);
        ++i;
      }
      while (j>x) {
        setvc(vc[i][j],1,2);
        --j;
      }
      while (i>x) {
        setvc(vc[i][j],0,1);
        --i;
      }
    } else {
      while (i<w-1-x) {
        setvc(vc[i][j],2,1);
        ++i;
      }
      while (j<h-1-x) {
        setvc(vc[i][j],3,2);
        ++j;
      }
      while (i>x) {
        setvc(vc[i][j],0,3);
        --i;
      }
      while (j>x) {
        setvc(vc[i][j],1,0);
        --j;
      }
    }
  }
}

vvi dist[MN];
vi pre;

int main() {
  scanf("%d%d%d%d",&h,&w,&n,&T);
  s = t = vv(n);
  rep(i,n) {
    s[i] = inV();
    t[i] = inV();
  }
  // o = vvi(h,vi(w));
  // rep(i,n) ov(s[i]) = (s[i]==t[i]?2:1);
  setxv();
  vs ans;
  pre = vi(n,-1);
  vi st(n);
  rep(k,n) {
    priority_queue<D> q;
    vvi& ds = dist[k];
    ds = vvi(h,vi(w,INF));
    ds[t[k].i][t[k].j] = 0;
    q.push(D(0,t[k]));
    while (sz(q)) {
      D d = q.top(); q.pop();
      int i = d.v.i, j = d.v.j;
      if (ds[i][j] != d.d) continue;
      rep(v,4) {
        int ni = i+di[v], nj = j+dj[v];
        if (ni<0||nj<0||ni>=h||nj>=w) continue;
        int nd = d.d+vc[ni][nj][v^2];
        if (ds[ni][nj] <= nd) continue;
        ds[ni][nj] = nd;
        q.push(D(nd,V(ni,nj)));
      }
    }
  }
  rep(ti,TURN+AD+ED) {
    o = vvi(h,vi(w));
    rep(i,n) ov(s[i]) = (st[i]==1?2:1);
    vector<P> ps;
    rep(k,n) {
      if (ti > TURN && st[k]) continue;
      priority_queue<D> q;
      vvi& ds = dist[k];
      if (ti > TURN) {
        ds = vvi(h,vi(w,INF));
        ds[t[k].i][t[k].j] = 0;
        q.push(D(0,t[k]));
        while (sz(q)) {
          D d = q.top(); q.pop();
          int i = d.v.i, j = d.v.j;
          if (ds[i][j] != d.d) continue;
          rep(v,4) {
            int ni = i+di[v], nj = j+dj[v];
            if (ni<0||nj<0||ni>=h||nj>=w) continue;
            if (o[ni][nj] == 2) continue;
            // if (ti > TURN && o[ni][nj] == 2) continue;
            int nd = d.d+vc[ni][nj][v^2];
            if (ds[ni][nj] <= nd) continue;
            ds[ni][nj] = nd;
            q.push(D(nd,V(ni,nj)));
          }
        }
      }
      ps.pb(P(-ds[s[k].i][s[k].j],k));
    }
    sort(rng(ps));
    bool upd = false;
    string now(n,'-');
    vi updx(n);
    for (P np : ps) {
      if (np.fi == -INF) continue;
      int k = np.se;
      if (s[k] == t[k]) {
        st[k] = 1;
        continue;
      }
      int best = INF, bv = 4;
      int& i = s[k].i;
      int& j = s[k].j;
      rep(v,4) {
        if (pre[k] == v) continue;
        int ni = i+di[v], nj = j+dj[v];
        if (ni<0||nj<0||ni>=h||nj>=w) continue;
        if (o[ni][nj]) continue;
        int nd = dist[k][ni][nj]+vc[i][j][v];
        if (nd <= best) {
          best = nd;
          bv = v;
        }
      }
      if (best == INF) continue;
      // if (best > -np.fi+100) continue;
      i += di[bv];
      j += dj[bv];
      now[k] = dc[bv];
      pre[k] = bv^2; updx[k] = 1;
      if (s[k] == t[k]) st[k] = 1;
      ov(s[k]) = -1;
      upd = true;
    }
    if (!upd) break;
    rep(i,n) if (!updx[i]) pre[i] = -1;
    if (ti > TURN) {
      rep(i,n) if (ti < TURN+AD && now[i] == '-' && st[i] && rand()%50==0) st[i] = -(MS-MS*ti/(TURN+AD));
      rep(i,n) if (st[i] < 0) {
        vi vls;
        rep(v,4) {
          int ni = s[i].i+di[v], nj = s[i].j+dj[v];
          if (ni<0||nj<0||ni>=h||nj>=w) continue;
          if (o[ni][nj]) continue;
          vls.pb(v);
        }
        if (sz(vls)) {
          int v = vls[rand()%sz(vls)];
          now[i] = dc[v];
          s[i].i += di[v];
          s[i].j += dj[v];
          ov(s[i]) = -1;
        }
        st[i]++;
      }
    }
    ans.pb(now);
    // cerr<<now<<endl;
  }
  cout<<sz(ans)<<endl;
  for (string ns : ans) cout<<ns<<endl;
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘V inV()’:
./Main.cpp:91:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&i,&j);
                      ^
./Main.cpp: In function ‘int main()’:
./Main.cpp:156:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d",&h,&w,&n,&T);
                                ^

Judge Result