#1101557 (C++23) No.3191 Operation Puzzle

提出ソース
結果

問題	No.3191 Operation Puzzle
ユーザー	zoidzium (zz)
提出日時	2025-06-27 21:48:27
言語	C++23 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	17 ms / 2,000 ms
コード長	17,247 bytes
コンパイル時間	4,203 ms
コンパイル使用メモリ	306,780 KB
実行使用メモリ	7,844 KB
最終ジャッジ日時	2025-06-27 21:48:34
合計ジャッジ時間	6,443 ms
ジャッジサーバーID （参考情報）	judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 2
other	AC * 45
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vl = vector<ll>;
using vul = vector<ull>;
using vs = vector<string>;
using vvs = vector<vs>;
using vd = vector<double>;
using vvl = vector<vl>;
using vvd = vector<vd>;
using xy = pair<ll, ll>;
using vxy = vector<xy>;
using vvxy = vector<vxy>;
using vvvl = vector<vvl>;

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define cnt(i, n, m) for (ll i = (n); i <= (m); i++)
#define each(ite, C) for (auto ite = (C).begin(); ite != (C).end(); ite++)
#define reach(ite, C) for (auto ite = (C).rbegin(); ite != (C).rend(); ite++)
#define yn(b) cout << (((b) > 0) ? "Yes" : "No") << endl;
#define square(a) ((a) * (a))
#define bfind(a, b) (((a) >> (b)) & 1ll)
#define bset(a, b, c) (((c) != 0) ? (a) | (1ll << (b)) : ~((~(a)) | (1 << (b))))
#define nth(a, b) (((a) >> (b)) & 1)

namespace zz_zout {

void ZOUT(const ll Hier, const ll PlaneHier, const string sep) {};

template <class Elm>
void ZOUT(const ll Hier, const ll PlaneHier, const string sep, const Elm elm) {
  cout << elm << sep;
  if (Hier >= PlaneHier) cout << endl;
};

void ZOUT(const ll Hier, const ll PlaneHier, const string sep, const char elm) {
  cout << elm << sep;
};
void ZOUT(const ll Hier, const ll PlaneHier, const string sep,
          const string elm) {
  cout << elm << sep;
};
void ZOUT(const ll Hier, const ll PlaneHier, const string sep, const ll elm) {
  cout << elm << sep;
};
void ZOUT(const ll Hier, const ll PlaneHier, const string sep, const ull elm) {
  cout << elm << sep;
};
void ZOUT(const ll Hier, const ll PlaneHier, const string sep, const int elm) {
  cout << elm << sep;
};
void ZOUT(const ll Hier, const ll PlaneHier, const string sep, const uint elm) {
  cout << elm << sep;
};

void ZOUT(const ll Hier, const ll PlaneHier, const string sep,
          const float elm) {
  cout << elm << sep;
};
void ZOUT(const ll Hier, const ll PlaneHier, const string sep,
          const double elm) {
  cout << elm << sep;
};

template <class Elm1, class Elm2>
void ZOUT(const ll Hier, const ll PlaneHier, const string sep,
          const pair<Elm1, Elm2> pr) {
  cout << "<" << sep;
  ZOUT(Hier + 1, PlaneHier, sep, pr.first);
  ZOUT(Hier + 1, PlaneHier, sep, pr.second);
  cout << ">" << sep;
  if (Hier >= PlaneHier) cout << endl;
};

template <class Elm>
void ZOUT(const ll Hier, const ll PlaneHier, const string sep,
          const vector<Elm> vec) {
  cout << "[" << sep;
  each(ite, vec) ZOUT(Hier + 1, PlaneHier, sep, *ite);
  cout << "]" << sep;
  if (Hier >= PlaneHier) cout << endl;
};

template <class Elm>
void ZOUT(const ll Hier, const ll PlaneHier, const string sep,
          const list<Elm> vec) {
  cout << "[" << sep;
  each(ite, vec) ZOUT(Hier + 1, PlaneHier, sep, *ite);
  cout << "]" << sep;
  if (Hier >= PlaneHier) cout << endl;
};

template <class Elm>
void ZOUT(const ll Hier, const ll PlaneHier, const string sep,
          const set<Elm> set) {
  cout << "[" << sep;
  each(ite, set) ZOUT(Hier + 1, PlaneHier, sep, *ite);
  cout << "]" << sep;
  if (Hier >= PlaneHier) cout << endl;
};
template <class Elm>
void ZOUT(const ll Hier, const ll PlaneHier, const string sep,
          const multiset<Elm> set) {
  cout << "[" << sep;
  each(ite, set) ZOUT(Hier + 1, PlaneHier, sep, *ite);
  cout << "]" << sep;
  if (Hier >= PlaneHier) cout << endl;
};
template <class Elm>
void ZOUT(const ll Hier, const ll PlaneHier, const string sep,
          const unordered_set<Elm> set) {
  cout << "[" << sep;
  each(ite, set) ZOUT(Hier + 1, PlaneHier, sep, *ite);
  cout << "]" << sep;
  if (Hier >= PlaneHier) cout << endl;
};
template <class Elm>
void ZOUT(const ll Hier, const ll PlaneHier, const string sep,
          const unordered_multiset<Elm> set) {
  cout << "[" << sep;
  each(ite, set) ZOUT(Hier + 1, PlaneHier, sep, *ite);
  cout << "]" << sep;
  if (Hier >= PlaneHier) cout << endl;
};

template <class Elm1, class Elm2>
void ZOUT(const ll Hier, const ll PlaneHier, const string sep,
          const map<Elm1, Elm2> map) {
  cout << "[" << sep;
  each(ite, map) ZOUT(Hier + 1, PlaneHier, sep, *ite);
  cout << "]" << sep;
  if (Hier >= PlaneHier) cout << endl;
};
template <class Elm1, class Elm2>
void ZOUT(const ll Hier, const ll PlaneHier, const string sep,
          const multimap<Elm1, Elm2> map) {
  cout << "[" << sep;
  each(ite, map) ZOUT(Hier + 1, PlaneHier, sep, *ite);
  cout << "]" << sep;
  if (Hier >= PlaneHier) cout << endl;
};
template <class Elm1, class Elm2>
void ZOUT(const ll Hier, const ll PlaneHier, const string sep,
          const unordered_map<Elm1, Elm2> map) {
  cout << "[" << sep;
  each(ite, map) ZOUT(Hier + 1, PlaneHier, sep, *ite);
  cout << "]" << sep;
  if (Hier >= PlaneHier) cout << endl;
};
template <class Elm1, class Elm2>
void ZOUT(const ll Hier, const ll PlaneHier, const string sep,
          const unordered_multimap<Elm1, Elm2> map) {
  cout << "[" << sep;
  each(ite, map) ZOUT(Hier + 1, PlaneHier, sep, *ite);
  cout << "]" << sep;
  if (Hier >= PlaneHier) cout << endl;
};

template <class Elm>
void ZOUT(const ll Hier, const ll PlaneHier, const string sep,
          const stack<Elm> csta) {
  stack<Elm> sta = csta;
  cout << "(" << sep;
  while (!sta.empty()) {
    ZOUT(Hier + 1, PlaneHier, sep, sta.top());
    sta.pop();
  }
  cout << "]" << sep;
  if (Hier >= PlaneHier) cout << endl;
};

template <class Elm>
void ZOUT(const ll Hier, const ll PlaneHier, const string sep,
          const queue<Elm> cque) {
  queue<Elm> que = cque;
  cout << "(" << sep;
  while (!que.empty()) {
    ZOUT(Hier + 1, PlaneHier, sep, que.front());
    que.pop();
  }
  cout << "]" << sep;
  if (Hier >= PlaneHier) cout << endl;
};
template <class Elm>
void ZOUT(const ll Hier, const ll PlaneHier, const string sep,
          const priority_queue<Elm> cque) {
  priority_queue<Elm> que = cque;
  cout << "(" << sep;
  while (!que.empty()) {
    ZOUT(Hier + 1, PlaneHier, sep, que.top());
    que.pop();
  }
  cout << "]" << sep;
  if (Hier >= PlaneHier) cout << endl;
};
template <class Elm>
void ZOUT(const ll Hier, const ll PlaneHier, const string sep,
          const deque<Elm> cque) {
  deque<Elm> que = cque;
  cout << "(" << sep;
  while (!que.empty()) {
    ZOUT(Hier + 1, PlaneHier, sep, que.front());
    que.pop_front();
  }
  cout << ")" << sep;
  if (Hier >= PlaneHier) cout << endl;
};

template <class Head, class... Tail>
void ZOUT(const ll Hier, const ll PlaneHier, const string sep, Head&& head,
          Tail&&... tails) {
  // zout(head);
  cout << head << sep;
  ZOUT(Hier + 1, PlaneHier, sep, forward<Tail>(tails)...);
  if (Hier >= PlaneHier) cout << endl;
};

////////////////////////////////////////
template <ll Hier = 10>
void zout() {
  cout << endl;
};

template <ll PlaneHier = 10, ll Sep = 1, class... Args>
void zout(Args&&... args) {
  ZOUT(1, PlaneHier, string(max<ll>(0, Sep), ' '), forward<Args>(args)...);
  cout << endl;
};

};  // namespace zz_zout
using namespace zz_zout;

namespace zz_time {
std::chrono::_V2::system_clock::time_point START_TIME =
    std::chrono::system_clock::now();

ll currentTime(std::chrono::_V2::system_clock::time_point st = START_TIME) {
  std::chrono::_V2::system_clock::time_point now =
      std::chrono::system_clock::now();
  return (ll)(std::chrono::duration_cast<std::chrono::milliseconds>(now - st)
                  .count());
};
};  // namespace zz_time
using namespace zz_time;

namespace zz_random {
std::random_device RANDOM_DEVICE;
std::mt19937 RANDOM_MT;
void setSeed(const ll& seed = RANDOM_DEVICE()) {
  RANDOM_MT = std::mt19937(seed);
};

std::uniform_int_distribution<int> createIntDistribution(const ll& L = 0,
                                                         const ll& R = 1) {
  return std::uniform_int_distribution<int>(L, R);
};
std::uniform_real_distribution<double> createDoubleDistribution(
    const double& L = 0.0, const double& R = 1.0) {
  return std::uniform_real_distribution<double>(L, R);
};
std::normal_distribution<double> createNormalDistribution(
    const double& average = 0.0, const double& standard_deviation = 1.0) {
  return std::normal_distribution<double>(average, standard_deviation);
}
bool getProbability(const double& p = 0.5) {
  return (createDoubleDistribution()(RANDOM_MT) <= 0.5);
}
};  // namespace zz_random
using namespace zz_random;

namespace zz_modulo {
class pp {
 public:
  ll e = 0;
  ll mod = 2;
  ll inv = 0;

  pp& operator=(const pp& x);
  pp operator+();
  pp operator-();
  template <typename T>
  pp& operator+=(const T& y);
  template <typename T>
  pp& operator-=(const T& y);
  template <typename T>
  pp& operator*=(const T& y);
  template <typename T>
  pp& operator/=(T& y);
  ll exp(ll x, ll I, ll modulo);
  pp exp(pp& x, ll I);
  pp exp(ll I);
  void cal_inv();
  pp inversion();
  string str() const;

  pp(const ll& elm = 0, const ll& modulo = 998244353, const ll& inversion = 0) {
    mod = modulo;
    e = elm;
    if (e < 0) {
      e = mod - ((-e) % mod);
    } else {
      e %= mod;
    }
    mod = modulo;
    if (inversion < 0) {
      cal_inv();
    } else if (inversion != 0) {
      inv = inversion;
    }
  };

  static vector<pp> create_vp(ll N, const ll& modulo);
  static pp chineseRemainderTheorem(vector<pp> vx);
  static pp garner(vector<pp> vx, const ll& mod);
};

pp& pp::operator=(const pp& x) {
  this->e = x.e;
  this->mod = x.mod;
  this->inv = x.inv;
  return *this;
};
pp operator+(const pp& x, const pp& y) {
  ll elm = x.e + y.e;
  if (elm > x.mod) elm -= x.mod;
  return pp(elm, x.mod);
};
template <typename T>
pp operator+(const pp& x, const T& y) {
  pp z(y, x.mod);
  return (x + z);
};
template <typename T>
pp operator+(const T& x, const pp& y) {
  pp z(x, y.mod);
  return (z + y);
};
template <typename T>
pp& pp::operator+=(const T& y) {
  *this = (*this) + y;
  return *this;
};

pp pp::operator+() { return *this; };

pp operator-(const pp& x, const pp& y) {
  ll elm = x.e - y.e;
  if (elm < 0) elm += x.mod;
  return pp(elm, x.mod);
};
template <typename T>
pp operator-(const pp& x, const T& y) {
  pp z(y, x.mod);
  return (x - z);
};
template <typename T>
pp operator-(const T& x, const pp& y) {
  pp z(x, y.mod);
  return (z - y);
};
template <typename T>
pp& pp::operator-=(const T& y) {
  *this = (*this) - y;
  return *this;
};

pp pp::operator-() { return (0 - (*this)); };

pp operator*(const pp& x, const pp& y) {
  return pp((x.e * y.e) % x.mod, x.mod, (x.inv * y.inv) % x.mod);
};
template <typename T>
pp operator*(const pp& x, const T& y) {
  pp z(y, x.mod);
  return (x * z);
};
template <typename T>
pp operator*(const T& x, const pp& y) {
  pp z(x, y.mod);
  return (z * x);
};
template <typename T>
pp& pp::operator*=(const T& y) {
  *this = (*this) * y;
  return *this;
};

pp operator/(const pp& x, pp& y) { return (x * y.inversion()); }
template <typename T>
pp operator/(const pp& x, T& y) {
  pp z(y, x.mod);
  return (x / z);
};
template <typename T>
pp operator/(const T& x, pp& y) {
  pp z(x, y.mod);
  return (z / y);
};
template <typename T>
pp& pp::operator/=(T& y) {
  *this = (*this) / y;
  return *this;
};

bool operator==(const pp& x, const pp& y) { return (x.e == y.e); }
template <typename T>
bool operator==(const T& x, const pp& y) {
  return (x == y.e);
};
template <typename T>
bool operator==(const pp& x, const T& y) {
  return (x.e == y);
};

bool operator!=(const pp& x, const pp& y) { return !(x == y); }
template <typename T>
bool operator!=(const T& x, const pp& y) {
  return !(x == y);
};
template <typename T>
bool operator!=(const pp& x, const T& y) {
  return !(x == y);
};

ll pp::exp(ll x, ll I, ll modulo) {
  ll y = 1;
  if (x < 0) {
    x = (modulo - ((-x) % modulo));
  } else {
    x %= modulo;
  }
  while (I > 0) {
    if (I & 1) {
      y = (y * x) % modulo;
    }
    x = (x * x) % modulo;
    I /= 2;
  };
  return y;
};

pp pp::exp(pp& x, ll I) {
  x.cal_inv();
  pp xx = x;
  pp y(1, xx.mod, 1);
  while (I > 0) {
    if (I & 1) {
      y = (y * xx);
    }
    xx = (xx * xx);
    I /= 2;
  };
  return y;
}

pp pp::exp(ll I) { return exp(*this, I); }

void pp::cal_inv() {
  if (this->inv <= 0) this->inv = exp(this->e, this->mod - 2, this->mod);
};

pp pp::inversion() {
  cal_inv();
  return pp(this->inv, this->mod, this->e);
}

string pp::str() const {
  return ("<epi " + to_string(e) + " \t" + to_string(mod) + " \t" +
          to_string(inv) + " >");
}

using vp = vector<zz_modulo::pp>;

vector<pp> pp::create_vp(ll N, const ll& modulo) {
  // m=m%i+m/i * i
  // 0- (m % i) = (m/i)*i
  cout << "!!" << endl;
  N = max<ll>(1, N);
  vector<pp> vec(N + 1);
  vec[0].e = 0;
  vec[0].mod = modulo;
  vec[0].inv = 1;
  vec[1].e = 1;
  vec[1].mod = modulo;
  vec[1].inv = 1;
  cnt(i, 2, N) {
    vec[i] = pp(i, modulo);
    cout << "@[" << i << "]=" << vec[i].str() << endl;
    cout << "---" << vec[modulo / i].str() << flush;
    cout << "  " << vec[modulo % i].str() << endl;
    vec[i].inv = (0 - ((modulo / i) * vec[modulo % i].inversion())).e;
    cout << " [" << i << "]=" << vec[i].str() << endl;
  }
  return vec;
};

pp chineseRemainderTheorem(vector<pp>& vx) {
  ll m = 1;
  each(ite, vx) m *= ite->mod;
  pp ans(0, m);
  each(ite, vx) {
    // ll Ai = R[i];
    // ll Mi = MMM / MM[i];
    // ll Ni = pp(Mi, MM[i]).inversion().e;

    // ANS += Ai * Mi * Ni;

    ll Ai = ite->e;
    ll Mi = m / ite->mod;
    ll Ni = pp(Mi, ite->mod, -1).inv;
    ans += pp(Ai * Mi * Ni, m);
    // zout(ans.str(), ite->str(), m, Ai, Mi, Ni);
  }

  return ans;
};

pp garner(vector<pp>& vx, const ll& mod) {
  ll N = vx.size();
  vector<vector<pp>> R(N, vector<pp>(N));
  rep(i, N) {
    cnt(j, i, N - 1) {
      if (i == j) {
        R[i][i] = vx[i].inversion();
      } else {
        R[i][j] = pp(vx[i].e, vx[j].mod, -1).inversion();
      }
      // zout("#ij=", i, j);
    }
  }
  vector<pp> X(N);
  rep(i, N) {
    X[i] = vx[i];
    rep(j, i) {
      // zout("ij=", i, j);
      X[i] = (X[i] - X[j].e) * R[j][i];
    }
    // cout << "x[" << i << "]=" << X[i].str() << endl;
  }
  // rep(i, N) zout(X[i].str());
  pp ANS(0, mod), P(1, mod);
  rep(i, N) {
    ANS += P.e * X[i].e;
    P *= vx[i].mod;
  }
  return ANS;
};

};  // namespace zz_modulo
using namespace zz_modulo;

namespace zz_prime {
class prime {
 public:
  static vl sieve;
  static vl p;
  static void set(ll N = 1000000) {
    N = max<ll>(2, N) + 1;
    sieve = vl(N, 0);
    p.clear();
    sieve[0] = 1;
    sieve[1] = 1;
    cnt(i, 2, N - 1) {
      if (sieve[i] == 0) {
        p.push_back(i);
        ll j = i;
        while (j < N) {
          if (sieve[j] == 0) sieve[j] = i;
          j += i;
        }
      }
    }
  };

  static bool isprime(ll x) {
    if (x <= 1) return false;
    if (sieve.empty()) set();
    if (x < sieve.size()) return (sieve[x] == x);
    each(ite, p) {
      if (x < (*ite) * (*ite)) return true;
      if ((x % (*ite)) == 0) return false;
    }
    return true;
  };

  static vxy factor(ll x) {
    x = max<ll>(1, x);
    if (sieve.empty()) set();

    map<ll, ll> MAP;
    each(ite, p) {
      if (x < sieve.size()) break;

      while ((x % (*ite)) == 0) {
        MAP[*ite]++;
        x /= *ite;
      }
    }

    if (x < sieve.size()) {
      while (x > 1) {
        MAP[sieve[x]]++;
        x /= sieve[x];
      }
    } else {
      MAP[x]++;
    }
    vxy fact;
    each(ite, MAP) fact.push_back(*ite);
    return fact;
  };

  static vl divisors(const vxy& fact) {
    vl ans(1, 1);
    function<void(const ll&, const ll&)> Func =
        [&fact, &ans, &Func](const ll& I, const ll& Elm) -> void {
      if (fact.empty()) return;
      ll Add = 1;

      if ((I + 1) < fact.size()) {
        Func(I + 1, Elm);
      } else {
        if (Elm != 1) ans.emplace_back(Elm);
      }

      cnt(i, 1, fact[I].second) {
        Add *= fact[I].first;
        if ((I + 1) < fact.size()) {
          Func(I + 1, Elm * Add);
        } else {
          ans.emplace_back(Elm * Add);
        }
      };
    };
    Func(0, 1);
    sort(ans.begin(), ans.end());
    return ans;
  };
};

vl prime::p;
vl prime::sieve;
}  // namespace zz_prime
using namespace zz_prime;

/////////////////////////////////////////////////

/////////////////////////////////////////////////

int main() {
  ll N, X;
  cin >> N;
  vl A(N);
  rep(i, N) cin >> A[i];
  cin >> X;

  vvl Tbl(4, vl(4, -1));
  function<void(const xy& AT, const ll&)> Func =
      [&N, &X, &A, &Tbl, &Func](const xy& AT, const ll& I) -> void {
    // cout << " @=" << AT.first << " " << AT.second << " " << I << endl;
    // zout<1>(Tbl);

    if (I == N) {
      if (Tbl[AT.first - 1][AT.second - 1] != -1 &&
          Tbl[AT.first - 1][AT.second - 1] != X)
        return;
      Tbl[AT.first - 1][AT.second - 1] = X;
      yn(true);
      rep(i, 4) {
        rep(j, 4) cout << (Tbl[i][j] == -1 ? 1 : Tbl[i][j]) << " ";
        // rep(j, 4) cout << Tbl[i][j] << " ";
        cout << endl;
      }
      exit(0);
    }
    if (Tbl[AT.first - 1][AT.second - 1] == -1) {
      cnt(B, 1, 4) {
        Tbl[AT.first - 1][AT.second - 1] = B;
        Func(xy{B, A[I]}, I + 1);
      }
      Tbl[AT.first - 1][AT.second - 1] = -1;
    } else {
      Func(xy{Tbl[AT.first - 1][AT.second - 1], A[I]}, I + 1);
    }
  };
  Func(xy{A[0], A[1]}, 2);
  yn(false);
  return 0;
}
yukicoder

結果

ソースコード
