SRM570 Div1 Easy

250

プログラムを何週か実行してこれまでと同じ向きで停止できれば、以降はそれの繰り返しになる。
実行回数 T を割り切れない様な周期での繰り返しになる場合は、残りを普通に実行してしまえばいい。

class RobotHerb {
public:
  long long getdist(int T, vector <int> a_)
  {
    vector<lli> a(a_.begin(), a_.end());
    const int D = 4;
    const lli di[D] = {0, +1, 0, -1};
    const lli dj[D] = {+1, 0, -1, 0};
    int dir = 0;

    lli i = 0, j = 0;
    lli run = 0;

    set<int> vis;
    while (!vis.count(dir) && T) {
      vis.insert(dir);
      for (int k = 0; k < a.size(); ++k) {
        i += a[k] * di[dir];
        j += a[k] * dj[dir];
        dir = (dir + a[k]) % D;
      }
      ++run;
      --T;
    }
    lli m_dist = labs(i) + labs(j);
    lli ret = m_dist;
    if (T) {
      ret += (T / run) * m_dist;
      T %= run;
      i = j = 0;
      while (T) {
        for (int k = 0; k < a.size(); ++k) {
          i += a[k] * di[dir];
          j += a[k] * dj[dir];
          dir = (dir + a[k]) % D;
        }
        --T;
      }
      ret += labs(i) + labs(j);
    }
    return ret;
  }



};