Submission #58801485

---

Source Code Expand

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

typedef int ll;
typedef long double ld;

#include <bits/stdc++.h>
using namespace std;
ll n, m, v;
set<pair<ll, ll>> s, t;
std::chrono::high_resolution_clock::time_point start;

ll dis(pair<ll, ll> x, pair<ll, ll> y) {
  return abs(x.first - y.first) + abs(x.second - y.second);
}

// xor128による乱数生成、周期は2^128-1
unsigned int randInt() {
  static unsigned int tx = 123456789, ty = 362436069, tz = 521288629,
                      tw = 88675123;
  unsigned int tt = (tx ^ (tx << 11));
  tx = ty;
  ty = tz;
  tz = tw;
  return (tw = (tw ^ (tw >> 19)) ^ (tt ^ (tt >> 8)));
}

int randInt(int minv, int maxv) { return randInt() % (maxv - minv + 1) + minv; }

ll min_score = 1e6;

bool inrange(ll x, ll y) {
  if (x < 0 || x >= n || y < 0 || y >= n) {
    return false;
  } else {
    return true;
  }
}

struct Ope {
  uint_fast8_t dir;
  uint_fast16_t rotateL;
  uint_fast16_t rotateR;
  uint_fast16_t grab;
};

pair<int, int> rotate90(int x, int y, int a, int b) {
  return {-(y - b) + a, (x - a) + b};
}
pair<ll, ll> rotate90(pair<ll, ll> a, pair<ll, ll> b) {
  return rotate90(a.first, a.second, b.first, b.second);
}

pair<int, int> rotate270(int x, int y, int a, int b) {
  return {(y - b) + a, -(x - a) + b};
}
pair<ll, ll> rotate270(pair<ll, ll> a, pair<ll, ll> b) {
  return rotate270(a.first, a.second, b.first, b.second);
}
pair<int, int> rotate180(int x, int y, int a, int b) {
  return {-(x - a) + a, -(y - b) + b};
}

pair<ll, ll> rotate180(pair<ll, ll> a, pair<ll, ll> b) {
  return rotate180(a.first, a.second, b.first, b.second);
}

map<char, int_fast8_t> ddd;

struct Tree {
  vector<pair<ll, ll>> pos;
  pair<ll, ll> init;
  vector<ll> par;
  set<pair<ll, ll>> s, t;
  string none = "";
  set<ll> have;
  set<ll> empty;
  set<ll> fushi;
  vector<ll> lens;
  vector<vector<ll>> child;
  void build(pair<ll, ll> initpos, ll size, vector<ll> length,
             vector<ll> parent, set<pair<ll, ll>> &ss, set<pair<ll, ll>> &tt) {
    init = initpos;
    for (auto &&e : ss) {
      s.insert(e);
    }
    for (auto &&e : tt) {
      t.insert(e);
    }
    d['R'] = {0, 1};
    d['L'] = {0, -1};
    d['U'] = {-1, 0};
    d['D'] = {1, 0};

    pos.resize(size);
    par.resize(size);
    lens.resize(size);
    child.resize(size);
    pos[0] = initpos;

    for (int i = 1; i < size; i++) {
      par[i] = parent[i - 1];
      pos[i] = {pos[par[i]].first, pos[par[i]].second + length[i - 1]};
      child[par[i]].push_back(i);
      lens[i] = length[i - 1];
      none += "..";
    }

    for (ll i = 1; i < size; i++) {
      if (child[i].size() == 0) {
        empty.insert(i);
      } else {
        fushi.insert(i);
      }
    }

    none += "..";
  }
  vector<Ope> history;

  ll ans_size() {
    if (ng) {
      return 1e6;
    } else {
      min_score = min(min_score, (ll)history.size());
      return history.size();
    }
  }

  void add_ope_newly(ll node, char c) {
    Ope o;
    o.dir = 0;
    o.rotateL = 0;
    o.rotateR = 0;
    o.grab = 0;
    if (node != 0 && c != 'P') {
      if (c == 'R') {
        o.rotateR |= 1 << (node - 1);
      } else if (c == 'L') {
        o.rotateL |= 1 << (node - 1);
      } else {
        cerr << "ERROR!!!" << endl;
      }
    } else if (node == 0 && c != 'P') {
      o.dir = ddd[c];
    } else if (c == 'P') {
      o.grab |= 1 << (node);
    } else {
      cerr << "ERRRORRRR!!" << endl;
    }
    history.push_back(o);
  }

  void add_ope(ll node, char c) {
    // 個々の処理を見直す
    // add_ope_newly(node, c);
    // return;
    if (history.size() == 0) {
      add_ope_newly(node, c);
    } else {
      auto now = history.back();
      if (node == 0 && c != 'P') {
        if (now.dir != 0 || now.grab != 0) {
          add_ope_newly(node, c);
        } else {
          now.dir = ddd[c];
          history.back() = now;
        }
      } else if (c == 'P') {
        if (now.grab & (1 << node)) {
          add_ope_newly(node, c);
        } else {
          now.grab |= 1 << (node);
          history.back() = now;
        }
      } else {
        bool ok = true;
        // TODO: 見直したい
        function<void(ll)> saiki = [&](ll cur) {
          if ((now.rotateL & (1 << (cur - 1))) ||
              (now.rotateR & (1 << (cur - 1))) || (now.grab & (1 << (cur)))) {
            ok = false;
            return;
          } else {
            for (auto &&e : child[cur]) {
              saiki(e);
              if (!ok) return;
            }
          }
        };
        saiki(node);

        if (ok) {
          if (c == 'R') {
            now.rotateR |= 1 << (node - 1);
          } else {
            now.rotateL |= 1 << (node - 1);
          }
          history.back() = now;
        } else {
          add_ope_newly(node, c);
        }
      }
    }
  }
  void rotate(ll x, bool c, ll from = -1) {
    if (from == -1) {
      if (c) {
        add_ope(x, 'L');
      } else {
        add_ope(x, 'R');
      }
    }
    pair<ll, ll> center;
    if (from == -1) {
      center = pos[par[x]];
      from = par[x];
    } else {
      center = pos[from];
    }
    if (c) {
      pos[x] =
          rotate90(pos[x].first, pos[x].second, center.first, center.second);
    } else {
      pos[x] =
          rotate270(pos[x].first, pos[x].second, center.first, center.second);
    }
    for (auto chi : child[x]) {
      rotate(chi, c, from);
    }
  }
  // TODO: change
  bool debug = false;

  void debug_output() {
    return;
    cerr << "debug" << endl;
    for (ll i = 0; i < (ll)pos.size(); i++) {
      cerr << i << " " << pos[i].first << " " << pos[i].second << endl;
    }
  }

  void grab(ll node) {
    if (debug) {
      if (have.find(node) != have.end()) {
        cerr << node << " already has " << endl;
      }
    }
    empty.erase(node);
    have.insert(node);
    add_ope(node, 'P');
  }
  void release(ll node) {
    if (debug) {
      if (empty.find(node) != empty.end()) {
        cerr << node << " already empty " << endl;
      }
    }
    have.erase(node);
    empty.insert(node);
    add_ope(node, 'P');
  }

  map<char, pair<ll, ll>> d;

  void move(char x) {
    pair<ll, ll> next = {pos[0].first + d[x].first,
                         pos[0].second + d[x].second};

    if (next.first < 0 || next.first >= n || next.second < 0 ||
        next.second >= n) {
      // ロジックの問題があるので回転させておちゃをにごす
      cerr << "unavoidable rotate" << endl;
      for (ll i = 1; i < (ll)pos.size(); i++) {
        rotate(i, true);
      }

      return;
    }
    add_ope(0, x);
    // cerr << "MOVE: " << x << endl;
    // cerr << "MOVE: " << x << endl;
    for (int i = 0; i < (ll)pos.size(); i++) {
      if (x == 'R') {
        pos[i].second++;
      } else if (x == 'L') {
        pos[i].second--;
      } else if (x == 'U') {
        pos[i].first--;
      } else if (x == 'D') {
        pos[i].first++;
      }
    }
  }

  void output() {
    tujituma();
    std::cout << (ll)pos.size() << std::endl;
    for (int i = 0; i < (ll)pos.size() - 1; i++) {
      std::cout << par[i + 1] << " " << lens[i + 1] << std::endl;
    }
    std::cout << init.first << " " << init.second << std::endl;

    for (auto &&i : history) {
      if (i.dir == 0) {
        cout << ".";
      } else {
        for (auto &&j : {'R', 'L', 'U', 'D'}) {
          if (ddd[j] == i.dir) cout << j;
        }
      }
      for (ll j = 0; j < (ll)pos.size() - 1; j++) {
        if (i.rotateL & (1 << j)) {
          cout << 'L';
        } else if (i.rotateR & (1 << j)) {
          cout << 'R';
        } else {
          cout << '.';
        }
      }
      for (ll j = 0; j < (ll)pos.size(); j++) {
        if (i.grab & (1 << j)) {
          cout << 'P';
        } else {
          cout << '.';
        }
      }
      cout << endl;
    }
  }
  bool ng = false;

  auto nearest(ll e, bool iss) {
    if (e == 0) {
      cerr << "ISSUE" << endl;
    }

    ll mi = 1000000;
    ll mi1 = 1000000;
    ll mi2 = 1000000;
    ll mi3 = 1000000;

    auto pos0 = pos[e];
    auto pos90 = rotate90(pos0, pos[par[e]]);
    auto pos270 = rotate270(pos0, pos[par[e]]);
    auto pos180 = rotate180(pos0, pos[par[e]]);

    tuple<ll, pair<ll, ll>, pair<ll, ll>, ll, ll> res;
    tuple<ll, pair<ll, ll>, pair<ll, ll>, ll, ll> res1;
    tuple<ll, pair<ll, ll>, pair<ll, ll>, ll, ll> res2;
    tuple<ll, pair<ll, ll>, pair<ll, ll>, ll, ll> res3;

    set<pair<ll, ll>> *se;
    if (iss) {
      se = &s;
    } else {
      se = &t;
    }

    bool first = true;
    for (auto &&i : *se) {
      ll dist0 = dis(i, pos0);  // Store the distances to avoid recalculating
      ll dist90 = dis(i, pos90);
      ll dist270 = dis(i, pos270);
      ll dist180 = dis(i, pos180);

      if (first) {
        res = make_tuple(mi, i, pos0, 0, e);
        res1 = make_tuple(mi1, i, pos90, 1, e);
        res2 = make_tuple(mi2, i, pos270, 2, e);
        res3 = make_tuple(mi3 + 1, i, pos180, 3, e);
        first = false;
      }

      // Update minimum distances and results
      if (dist0 < mi) {
        mi = dist0;
        res = make_tuple(mi, i, pos0, 0, e);
      }
      if (dist90 < mi1) {
        mi1 = dist90;
        res1 = make_tuple(mi1, i, pos90, 1, e);
      }
      if (dist270 < mi2) {
        mi2 = dist270;
        res2 = make_tuple(mi2, i, pos270, 2, e);
      }
      if (dist180 < mi3) {
        mi3 = dist180;
        res3 = make_tuple(mi3 + 1, i, pos180, 3, e);
      }

      // Early exit if the minimum distance is zero
      if (mi == 0) break;
    }

    return make_tuple(res, res1, res2, res3);
  }

  void grab_and_release() {
    vector<ll> grabs;
    for (auto e : empty) {
      auto pos0 = pos[e];
      auto pos90 = rotate90(pos0, pos[par[e]]);
      auto pos270 = rotate270(pos0, pos[par[e]]);
      if (s.find(pos0) != s.end()) {
        grabs.push_back(e);
        s.erase(pos0);
      } else if (s.find(pos90) != s.end()) {
        rotate(e, true);
        grabs.push_back(e);
        s.erase(pos90);
      } else if (s.find(pos270) != s.end()) {
        rotate(e, false);
        grabs.push_back(e);
        s.erase(pos270);
      } else {
      }
    }
    for (auto e : grabs) {
      grab(e);
    }

    vector<ll> releases;

    for (auto e : have) {
      auto pos0 = pos[e];
      auto pos90 = rotate90(pos0, pos[par[e]]);
      auto pos270 = rotate270(pos0, pos[par[e]]);
      if (t.find(pos0) != t.end()) {
        releases.push_back(e);
        t.erase(pos0);
      } else if (t.find(pos90) != t.end()) {
        rotate(e, true);
        releases.push_back(e);
        t.erase(pos90);
      } else if (t.find(pos270) != t.end()) {
        rotate(e, false);
        releases.push_back(e);
        t.erase(pos270);
      } else {
      }
    }

    for (auto e : releases) {
      release(e);
    }
  }
  bool prioritize_pick = true;
  bool move_tree() {
    if (have.size() == 0) prioritize_pick = true;

    pair<ll, ll> near = {-1, -1};
    pair<ll, ll> from = {-1, -1};
    prioritize_pick = prioritize_pick && s.size() > 0 && empty.size() > 0;

    set<tuple<ll, pair<ll, ll>, pair<ll, ll>, ll, ll>> cost_pair_nanila;
    if (s.size() > 0) {
      for (auto e : empty) {
        auto [r1, r2, r3, r4] = nearest(e, true);
        cost_pair_nanila.insert(r1);
        cost_pair_nanila.insert(r2);
        cost_pair_nanila.insert(r3);
        cost_pair_nanila.insert(r4);
      }
    }
    if (t.size() > 0) {
      for (auto e : have) {
        auto [r1, r2, r3, r4] = nearest(e, false);
        cost_pair_nanila.insert(r1);
        cost_pair_nanila.insert(r2);
        cost_pair_nanila.insert(r3);
        cost_pair_nanila.insert(r4);
      }
    }

    // bool find = false;

    if (cost_pair_nanila.size() == 0) {
      cerr << "no_found" << endl;
      return false;
    }

    for (auto e : cost_pair_nanila) {
      auto [cost, pair, ff, kaiten, node] = e;
      // if (min_score != 0) cerr << "node:" << node << endl;
      if (!inrange(pair.first - ff.first + pos[0].first,
                   pair.second - ff.second + pos[0].second))
        continue;
      near = pair;
      if (kaiten == 1) {
        rotate(node, true);
      } else if (kaiten == 2) {
        rotate(node, false);
      } else if (kaiten == 3) {
        rotate(node, false);
        rotate(node, false);
      }
      from = pos[node];
      break;
    }

    // if(find)

    // if (min_score != 0) {
    //   cerr << from.first << " from " << from.second << endl;
    //   cerr << near.first << " near " << near.second << endl;
    //   cerr << empty.size() << " " << have.size() << " " << s.size() << " "
    //        << t.size() << endl;
    // }
    // cerr << "start move" << endl;
    if (near.first - from.first > 0) {
      move('D');
      return true;
    } else if (near.first - from.first < 0) {
      move('U');
      return true;
    } else if (near.second - from.second > 0) {
      move('R');
      return true;
    } else if (near.second - from.second < 0) {
      move('L');
      return true;
    } else {
      return false;
    }
  }
  ll out = 0;

  // 小さいほうがいい
  // ll score_value() { return t.size() + s.size() + (ll)history.size(); }
  ll score_value() {
    if (ng) {
      return 10000000;
    } else {
      return t.size() + s.size() + (ll)history.size();
    }
  }

  void step0() {
    if ((ll)history.size() > min_score || out > 10) {
      ng = true;
      return;
    }
    if (t.size() == 0) return;
    if (ng) return;
    grab_and_release();
  }

  void step1() {
    if (t.size() == 0) return;
    if (ng) return;
    if (!move_tree()) {
      out++;
    } else {
      out = 0;
    }
  }
  void tujituma(){
    ll index = 0;
    vector<Ope> ne;
    while(index<(ll)history.size()){
      auto target = history[index];

      // 何かを掴む処理をしている
      if(target.grab){
        index++;
        ne.push_back(target);
        continue;
      }
      ll now = index;
      vector<Ope> oo;
      pair<ll,ll> idou = {0,0};
      // rootは数えない
  //     ddd['R'] = 1;
  // ddd['L'] = 2;
  // ddd['U'] = 3;
  // ddd['D'] = 4;
      vector<ll> rota((ll)pos.size()-1, 4000);
      while(now<(ll)history.size()){
        auto cur = history[now];
        if(history[now].grab==0){
          now++;
          if(cur.dir==1){
            idou.second++;
          }else if(cur.dir==2){
            idou.second--;
          }else if(cur.dir==3){
            idou.first++;
          }else if(cur.dir==4){
            idou.first--;
          }
          for(ll ii = 0;ii<(ll)pos.size()-1;ii++){
            if(cur.rotateR &(1<<ii)){
              rota[ii]++;
            }
            if(cur.rotateL &(1<<ii)){
              rota[ii]--;
            }
          }
        }else{
          if(cur.dir==1){
            idou.second++;
          }else if(cur.dir==2){
            idou.second--;
          }else if(cur.dir==3){
            idou.first++;
          }else if(cur.dir==4){
            idou.first--;
          }
          for(ll ii = 0;ii<(ll)pos.size()-1;ii++){
            if(cur.rotateR &(1<<ii)){
              rota[ii]++;
            }
            if(cur.rotateL &(1<<ii)){
              rota[ii]--;
            }
          }
          break;
        }
      }
      while(true){
        Ope co;
        co.dir = 0;
        co.rotateR = 0;
        co.rotateL = 0;
        co.grab = 0;
        bool nochange=false;
        if(idou.first>0){
          co.dir = 3;
          idou.first--;
        }else if(idou.first<0){
          co.dir = 4;
          idou.first++;
        }else if(idou.second>0){
          co.dir = 1;
          idou.second--;
        }else if(idou.second<0){
          co.dir = 2;
          idou.second++;
        }else{
          nochange=true;
        }
        for(ll ii =0;ii<(ll)pos.size()-1;ii++){
          if(rota[ii]%4==3){
            nochange=false;
            co.rotateL += 1<<ii;
            rota[ii]=0;
          }else if(rota[ii]%4==2){
            rota[ii]=1;
            nochange=false;
            co.rotateR += 1<<ii;
          }else if(rota[ii]%4==1){
            rota[ii]=0;
            nochange=false;
            co.rotateR += 1<<ii;
          }
        }
        if(nochange)break;
        ne.push_back(co);
      }
      ne.back().grab = history[now].grab;
      index = now+1;
    }
    history = ne;
  }
};

const ll TRIAL = 15;
ll SAKI = 2;
void solve_tree(Tree &tree) {
  tree.step0();
  ll count = 0;
  while (tree.t.size() > 0 && !tree.ng) {
    count++;
    ll mi = 1000000000;
    Tree next = tree;
    if(count%50==0){
      auto end = std::chrono::high_resolution_clock::now();
      auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();

      // cerr<<duration<<endl;
      if(duration>2800){
        tree.ng = true;
        return;
      }
    }

    for (ll i = 0; i < TRIAL; i++) {
      Tree temp = tree;
      Tree temp1;
      for (ll j = 0; j < SAKI; j++) {
        if (temp.t.size() == 0 || temp.ng) break;
        for (auto &&e : temp.fushi) {
          if (randInt(1, 100) < 33) {
            temp.rotate(e, true);
          } else if (randInt(1, 100) < 33) {
            temp.rotate(e, false);
          }
        }
        temp.step1();
        temp.step0();
        if(j==0){
        temp1 = temp;

        }
      }
      if (mi > temp.score_value()) {
        mi = temp.score_value();
        next =temp1;
      }
    }

    tree = next;
  }
}


const bool DEBUG = false;
signed main() {
  ddd['R'] = 1;
  ddd['L'] = 2;
  ddd['U'] = 3;
  ddd['D'] = 4;

  
 start = std::chrono::high_resolution_clock::now();

  std::cin >> n >> m >> v;
  for (int i = 0; i < n; i++) {
    string S;
    std::cin >> S;
    for (int j = 0; j < n; j++) {
      if (S[j] == '1') {
        s.insert({i, j});
      }
    }
  }
  for (int i = 0; i < n; i++) {
    string S;
    std::cin >> S;
    for (int j = 0; j < n; j++) {
      if (S[j] == '1') {
        if (s.find({i, j}) != s.end()) {
          s.erase({i, j});
        } else {
          t.insert({i, j});
        }
      }
    }
  }
  if(t.size()>=250){
    SAKI=3;
  }
  Tree ans;
  vector<ll> length(v - 1);
  vector<ll> parent(v - 1);
  for (ll i = 0; i < v - 1; i++) {
    length[i] = n / 2 + i / 4;
    // if (i > v / 2) {
    //   parent[i] = 1;
    // }
  }
  pair<ll, ll> initPos = {n / 2, n / 2};
  ans.build(initPos, v, length, parent, s, t);
  solve_tree(ans);
  ll score = ans.ans_size();
  // ll score = 1000000;
  for (ll i = 0; i < 10000000; i++) {
     auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();

    // cerr<<duration<<endl;
    if(duration>2800){
      break;
    }
    // if (true) {
    //   auto end = std::chrono::high_resolution_clock::now();
    //   auto duration =
    //       std::chrono::duration_cast<std::chrono::milliseconds>(end - start)
    //           .count();
    //   cerr<<duration<<endl;
    //   if (duration > 2500) {
    //     // cerr << "i: " << i << endl;
    //     break;
    //   }
    // }
    auto mpos = initPos;
    auto ml = length;
    auto mp = parent;

    for (ll j = 0; j < v - 1; j++) {
      // if (randInt(0, 100) < 80) {
      length[j] = randInt(1, n * 2 / 3);
      // }
      // if (randInt(0, 100) < 80) {
      // if (i % 2 == 0) {
      //   parent[j] = 0;
      // } else {
      // parent[j] = randInt(0, min((int)j, (int)1));
      // parent[j] = min((int)j, (int)1);
      // if(j<v/4){
      //   parent[j] = j;
      // }else{
      //   parent[j] = min((int)j, (int)v / 4);
      // }
      // if (i % 2 == 0) {
      parent[j] = min((int)j, (int)v / 3);
      // } else {
      //   parent[j] = randInt(0, min(0, (int)j));
      // }
      // }
    }

    // if (randInt(0, 100) < 80) {
    initPos = {min(n - 1, max(0, n / 2 + randInt(-20, 20))),
               min(n - 1, max(0, n / 2 + randInt(-20, 20)))};
    // }
    Tree tree;
    tree.build(initPos, v, length, parent, s, t);
    solve_tree(tree);
    ll tmp_score = tree.ans_size();
    // cerr << tmp_score << endl;
    if (tmp_score < score) {
      score = tmp_score;
      ans = tree;
      if (DEBUG) cerr << "#";
    } else {
      if (DEBUG) cerr << ".";
      initPos = mpos;
      length = ml;
      parent = mp;
    }
  }
  if (DEBUG) cerr << endl;

  ans.output();
};

Submission Info

Judge Result