Submission #1174165

---

Source Code Expand

#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#include <sys/time.h>
#define REP(i,n) for(int i=0; i<(int)(n); i++)

#include <cstdio>
inline int getInt(){ int s; scanf("%d", &s); return s; }

#include <set>

const int _dx[] = {0,1,0,-1,0};
const int _dy[] = {-1,0,1,0,0};
#define IN(x,s,g) ((x) >= (s) && (x) < (g))
#define ISIN(x,y,w,h) (IN((x),0,(w)) && IN((y),0,(h)))

using namespace std;

int h, w, k, t;
int x[450];
int y[450];
int xd[450];
int yd[450];
int phase = 0;

char buff[512];

#define MOVE(x, y, xx, yy) for(int _d = 0, xx, yy; xx = (x) + _dx[_d], yy = (y) + _dy[_d], _d < 4 && ISIN(xx, yy, w, h); _d++)

int board[30][30];

vector<int> randomV(int n){
  vector<int> r(n);
  REP(i,n) r[i] = i;
  random_shuffle(r.begin(), r.end());
  return r;
}

class Matching{
  typedef vector<vector<int> > G;

  vector<bool> visited;

  const G &g; //g[i][j] = k <==> i is connected to k
  int n;      //number of node
  int m;      //number of left node

  bool augment(int left) {
    if (left < 0)
      return true;
    if (visited[left])
      return false;
    visited[left] = true;
    REP(i, g[left].size()) {
      int right = g[left][i];
      if (augment(matching[right])) {
        matching[right] = left;
        return true;
      }
    }
    return false;
  }

public:
  vector<int> matching;

  explicit Matching(const G &graph, int mm)
    : g(graph), m(mm){
    n = graph.size();
  }

  int solve() {
    int matches = 0;
    matching = vector<int>(n,-1);
    visited  = vector<bool>(n);
    REP(left, m) {
      visited.assign(n, false);
      if (augment(left))
        matches++;
    }
    return matches;
  }
};

string solve0(int turn){
  int cnt = 0;
  vector<int> decided(k, 0);
  vector<vector<set<int> > > cand(h, vector<set<int> >(w));

  memset(board, -1, sizeof(board));
  REP(i,k) board[y[i]][x[i]] = i;

  vector<vector<int> > g(k + h * w);
  auto index = [&](int x, int y){ return k + y * w + x; };

  REP(i,k){
    if((x[i] + y[i]) % 2 == turn % 2){
      const int j = index(x[i], y[i]);
      g[i].push_back(j);
      g[j].push_back(i);
    }else{
      const vector<int> d = randomV(4);
      REP(dd,4){
        const int xx = x[i] + _dx[d[dd]];
        const int yy = y[i] + _dy[d[dd]];
        if(!ISIN(xx, yy, w, h)) continue;
        if(board[yy][xx] == -1){
          const int j = index(xx, yy);
          g[i].push_back(j);
          g[j].push_back(i);
        }
      }
    }
  }

  REP(i,k) buff[i] = '-';

  Matching matching(g, k);
  const int t = matching.solve();

  if(t == k) phase = 1;

  REP(i,h) REP(j,w){
    const int o = matching.matching[k + i * w + j];
    if(o != -1){
      const int xx = x[o];
      const int yy = y[o];

      if(yy == i){
        if(xx + 1 == j){
          buff[o] = 'R';
        }else if(xx - 1 == j){
          buff[o] = 'L';
        }
      }else if(xx == j){
        if(yy + 1 == i){
          buff[o] = 'D';
        }else if(yy - 1 == i){
          buff[o] = 'U';
        }
      }

      x[o] = j;
      y[o] = i;
    }
  }

  return buff;
}

double calc(int turn){
  const double pt = 10 + turn * 0.01;
  double pd = 20;
  REP(i,k){
    pd += std::abs(x[i] - xd[i]) + std::abs(y[i] - yd[i]);
  }
  return 1e7 / (pd * pt);
}

void debug(){
  memset(board, -1, sizeof(board));
  REP(i,k) board[y[i]][x[i]] = i;

  REP(i,h) {
    REP(j,w){
      if(board[i][j] == -1) putchar('.');
      else putchar('+');
    }
    puts("");
  }
}

struct Edge{
  int cap; // capacity
  int to;
  int rev; // reverse edge id

  Edge(){}
  Edge(int c, int t, int r) :
    cap(c), to(t), rev(r){}
};

struct CostEdge : public Edge{
  int cost;
  CostEdge() : Edge() {}
  CostEdge(int c, int t, int cs, int r) :
    Edge(c, t, r), cost(cs){}
};

template<class E> // Edge type
class Graph{
public:
  typedef std::vector<std::vector<E> > G;

private:
  G g;

public:
  Graph(int n) : g(G(n)) {}

  void addEdge(int from, int to, int cap){
    g[from].push_back(E(cap, to, g[to].size()));
    g[to].push_back(E(0, from, g[from].size() - 1));
  }

  void addEdge(int from, int to, int cap, int cost){
    g[from].push_back(E(cap, to, cost, g[to].size()));
    g[to].push_back(E(0, from, -cost, g[from].size() - 1));
  }

  G &getRowGraph(){
    return g;
  }
};

#include <queue>
#include <climits>

template<class E>
int minCostFlow(Graph<E> &graph, int s, int t, int f){
  typedef pair<int, int> P;
  typename Graph<E>::G &g = graph.getRowGraph();
  int n = g.size();
  int res = 0;
  vector<int> h(n, 0);
  vector<int> prevv(n);
  vector<int> preve(n);
  const int inf = 10000000;

  while(f > 0){
    priority_queue<P, vector<P>, greater<P> > que;
    vector<int> dist(n, inf);
    dist[s] = 0;
    que.push(P(0, s));

    while(!que.empty()){
      P p   = que.top(); que.pop();
      int v = p.second;
      if(dist[v] < p.first) continue;
      for(int i = 0; i < (int)g[v].size(); i++){
        E &e = g[v][i];

        if(e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]){
          dist[e.to]  = dist[v] + e.cost + h[v] - h[e.to];
          prevv[e.to] = v;
          preve[e.to] = i;
          que.push(P(dist[e.to], e.to));
        }
      }
    }
    if(dist[t] == inf){
      return -1;
    }

    for(int v = 0; v < n; v++) h[v] += dist[v];

    int d = f;
    for(int v = t; v != s; v = prevv[v]){
      d = min(d, g[prevv[v]][preve[v]].cap);
    }

    f   -= d;
    res += d * h[t];

    for(int v = t; v != s; v = prevv[v]){
      E &e = g[prevv[v]][preve[v]];
      e.cap -= d;
      g[v][e.rev].cap += d;
    }
  }
  return res;
}



string solve1(int turn){
  Graph<CostEdge> g(2 + k + h * w);
  const int src = k + h * w;
  const int dst = k + h * w + 1;

  auto index = [&](int x, int y){ return k + y * w + x; };

  REP(i,k){
    const vector<int> d = randomV(4);
    REP(dd,4){
      const int xx = x[i] + _dx[d[dd]];
      const int yy = y[i] + _dy[d[dd]];
      if(!ISIN(xx, yy, w, h)) continue;
      const int j = index(xx, yy);
      const int cost = std::abs(yy - yd[i]) + std::abs(xx - xd[i]);
      g.addEdge(i, j, 1, cost);
    }
  }

  REP(i,k){
    g.addEdge(src, i, 1, 0);
  }

  REP(i,h) REP(j,w){
    g.addEdge(index(j, i), dst, 1, 0);
  }

  const int cost = minCostFlow(g, src, dst, k);
  // printf("cost: %d\n", cost);

  const auto gg = g.getRowGraph();
  REP(i,k){
    buff[i] = '-';
    REP(j,gg[i].size()){
      if(gg[i][j].cap == 0){
        const int t = gg[i][j].to;
        const int xx = (t - k) % w;
        const int yy = (t - k) / w;

        if(yy == y[i]){
          if(x[i] + 1 == xx){
            buff[i] = 'R';
          }else if(x[i] - 1 == xx){
            buff[i] = 'L';
          }
        }else if(xx == x[i]){
          if(y[i] + 1 == yy){
            buff[i] = 'D';
          }else if(y[i] - 1 == yy){
            buff[i] = 'U';
          }
        }

        x[i] = xx;
        y[i] = yy;
        break;
      }
    }
  }

  return buff;
}

string solve2(int turn){
  REP(i,k){
    buff[i] = '-';
    if(x[i] == xd[i]){
      if(y[i] + 1 == yd[i]) buff[i] = 'D';
      else if(y[i] - 1 == yd[i]) buff[i] = 'U';
    }else if(y[i] == yd[i]){
      if(x[i] + 1 == xd[i]) buff[i] = 'R';
      else if(x[i] - 1 == xd[i]) buff[i] = 'L';
    }
  }
  return buff;
}

double cur(){
  struct timeval tm;
  gettimeofday(&tm, NULL);
  return tm.tv_sec + tm.tv_usec * 1e-6;
}

int main(){
  const int h = ::h = getInt();
  const int w = ::w = getInt();
  const int k = ::k = getInt();
  const int t = ::t = getInt();

  vector<string> anss;
  vector<double> scores;

  REP(i,k){
    y[i] = getInt() - 1;
    x[i] = getInt() - 1;
    yd[i] = getInt() - 1;
    xd[i] = getInt() - 1;
  }

  const double start = cur();

  for(int i = 0; i < t && cur() - start < 3.7; i++){
    if(phase == 0){
      const string s = solve0(i);
      const double score = calc(i + 1);
      anss.push_back(s);
      scores.push_back(score);
    }else if(phase == 1){
      const string s = solve1(i);

      bool ok = true;
      int cost = 0;
      REP(i,k){
        const int t = std::abs(x[i] - xd[i]) + std::abs(y[i] - yd[i]);
        cost += t;
        if(t > 1) ok = false;
      }
      if(ok) phase = 2;
      const double score = calc(i + 1);

      anss.push_back(s);
      scores.push_back(score);
    }else{
      const string s = solve2(i);
      const double score = calc(i + 1);
      anss.push_back(s);
      scores.push_back(score);
    }
  }

  const int tn = max_element(scores.begin(), scores.end()) - scores.begin();
  printf("%d\n", tn);
  REP(i,tn) puts(anss[i].c_str());

  return 0;
}

Submission Info

Judge Result