#1085332 (C++23) No.3143 Colorless Green Parentheses Sleep Furiously

提出ソース
結果

問題	No.3143 Colorless Green Parentheses Sleep Furiously
ユーザー	zoidzium (zz)
提出日時	2025-05-16 22:11:55
言語	C++23 (gcc 13.3.0 + boost 1.87.0)
結果	WA (最新) AC (最初)
実行時間	-
コード長	19,537 bytes
コンパイル時間	3,831 ms
コンパイル使用メモリ	302,480 KB
実行使用メモリ	7,848 KB
最終ジャッジ日時	2025-05-17 00:29:16
合計ジャッジ時間	6,157 ms
ジャッジサーバーID （参考情報）	judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 3
other	AC * 48 WA * 1
権限があれば一括ダウンロードができます
ソースコード

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 out(const ll& showBit, const ll& Hier, const string& header,
         const string& space, const string& endline) {};

template <typename T>
void out(const ll& showBit, const ll& Hier, const string& header,
         const string& space, const string& endline, const T& x) {
  if (showBit == 0) {
    cout << header << x << space << endline;
  } else {
    cout << header;
    bitset<64> bit(x);
    rep(i, showBit) cout << bit[i];
    cout << space << endline;
  }
};

template <typename E1, typename E2>
void out(const ll& showBit, const ll& Hier, const string& header,
         const string& space, const string& endline, const pair<E1, E2>& x) {
  cout << header << "< ";
  out(showBit, 0, "", " ", "", x.first);
  out(showBit, 0, "", " ", "", x.second);
  cout << ">" << space << endline;
};

template <typename E>
void out(const ll& showBit, const ll& Hier, const string& header,
         const string& space, const string& endline, const vector<E>& x) {
  cout << header << "[" << space;
  if (Hier) cout << endline;
  for (E xx : x) {
    if (Hier) {
      if (Hier > 0) {
        out(showBit, Hier - 1, header + "  ", space, endline, xx);
      }
    } else {
      out(showBit, 0, "", space, "", xx);
    }
  }
  if (Hier) cout << header;
  cout << "]" << space << endline;
};

template <typename E>
void out(const ll& showBit, const ll& Hier, const string& header,
         const string& space, const string& endline, const set<E>& x) {
  cout << header << "{" << space;
  if (Hier) cout << endline;
  for (E xx : x) {
    if (Hier) {
      if (Hier > 0) {
        out(showBit, Hier - 1, header + "  ", space, endline, xx);
      }
    } else {
      out(showBit, 0, "", space, "", xx);
    }
  }
  if (Hier) cout << header;
  cout << "}" << space;
  if (Hier) cout << endline;
};
template <typename E>
void out(const ll& showBit, const ll& Hier, const string& header,
         const string& space, const string& endline, const multiset<E>& x) {
  cout << header << "{" << space;
  if (Hier) cout << endline;
  for (E xx : x) {
    if (Hier) {
      if (Hier > 0) {
        out(showBit, Hier - 1, header + "  ", space, endline, xx);
      }
    } else {
      out(showBit, 0, "", space, "", xx);
    }
  }
  if (Hier) cout << header;
  cout << "}" << space;
  if (Hier) cout << endline;
};
template <typename E>
void out(const ll& showBit, const ll& Hier, const string& header,
         const string& space, const string& endline,
         const unordered_set<E>& x) {
  cout << header << "{" << space;
  if (Hier) cout << endline;
  for (E xx : x) {
    if (Hier) {
      if (Hier > 0) {
        out(showBit, Hier - 1, header + "  ", space, endline, xx);
      }
    } else {
      out(showBit, 0, "", space, "", xx);
    }
  }
  if (Hier) cout << header;
  cout << "}" << space;
  if (Hier) cout << endline;
};
template <typename E>
void out(const ll& showBit, const ll& Hier, const string& header,
         const string& space, const string& endline,
         const unordered_multiset<E>& x) {
  cout << header << "{" << space;
  if (Hier) cout << endline;
  for (E xx : x) {
    if (Hier) {
      if (Hier > 0) {
        out(showBit, Hier - 1, header + "  ", space, endline, xx);
      }
    } else {
      out(showBit, 0, "", space, "", xx);
    }
  }
  if (Hier) cout << header;
  cout << "}" << space;
  if (Hier) cout << endline;
};

template <typename E1, typename E2>
void out(const ll& showBit, const ll& Hier, const string& header,
         const string& space, const string& endline, const map<E1, E2>& x) {
  cout << header << "{" << space;
  if (Hier) cout << endline;
  for (pair<E1, E2> xx : x) {
    if (Hier) {
      if (Hier > 0) {
        out(showBit, Hier - 1, header + "  ", space, endline, xx);
      }
    } else {
      out(showBit, 0, "", space, "", xx);
    }
  }
  if (Hier) cout << header;
  cout << "}" << space;
  if (Hier) cout << endline;
};
template <typename E1, typename E2>
void out(const ll& showBit, const ll& Hier, const string& header,
         const string& space, const string& endline,
         const multimap<E1, E2>& x) {
  cout << header << "{" << space;
  if (Hier) cout << endline;
  for (pair<E1, E2> xx : x) {
    if (Hier) {
      if (Hier > 0) {
        out(showBit, Hier - 1, header + "  ", space, endline, xx);
      }
    } else {
      out(showBit, 0, "", space, "", xx);
    }
  }
  if (Hier) cout << header;
  cout << "}" << space;
  if (Hier) cout << endline;
};
template <typename E1, typename E2>
void out(const ll& showBit, const ll& Hier, const string& header,
         const string& space, const string& endline,
         const unordered_map<E1, E2>& x) {
  cout << header << "{" << space;
  if (Hier) cout << endline;
  for (pair<E1, E2> xx : x) {
    if (Hier) {
      if (Hier > 0) {
        out(showBit, Hier - 1, header + "  ", space, endline, xx);
      }
    } else {
      out(showBit, 0, "", space, "", xx);
    }
  }
  if (Hier) cout << header;
  cout << "}" << space;
  if (Hier) cout << endline;
};
template <typename E1, typename E2>
void out(const ll& showBit, const ll& Hier, const string& header,
         const string& space, const string& endline,
         const unordered_multimap<E1, E2>& x) {
  cout << header << "{" << space;
  if (Hier) cout << endline;
  for (pair<E1, E2> xx : x) {
    if (Hier) {
      if (Hier > 0) {
        out(showBit, Hier - 1, header + "  ", space, endline, xx);
      }
    } else {
      out(showBit, 0, "", space, "", xx);
    }
  }
  if (Hier) cout << header;
  cout << "}" << space;
  if (Hier) cout << endline;
};

template <typename E>
void out(const ll& showBit, const ll& Hier, const string& header,
         const string& space, const string& endline, const stack<E>& x) {
  cout << header << "(" << space;
  if (Hier) cout << endline;
  stack<E> sta = x;
  while (!sta.empty()) {
    E xx = sta.top();
    sta.pop();
    if (Hier) {
      if (Hier > 0) {
        out(showBit, Hier - 1, header + "  ", space, endline, xx);
      }
    } else {
      out(showBit, 0, "", space, "", xx);
    }
  }
  if (Hier) cout << header;
  cout << "]" << space;
  if (Hier) cout << endline;
};
template <typename E>
void out(const ll& showBit, const ll& Hier, const string& header,
         const string& space, const string& endline, const queue<E>& x) {
  cout << header << "(" << space;
  if (Hier) cout << endline;
  queue<E> que = x;
  while (!que.empty()) {
    E xx = que.front();
    que.pop();
    if (Hier) {
      if (Hier > 0) {
        out(showBit, Hier - 1, header + "  ", space, endline, xx);
      }
    } else {
      out(showBit, 0, "", space, "", xx);
    }
  }
  if (Hier) cout << header;
  cout << "]" << space;
  if (Hier) cout << endline;
};
template <typename E>
void out(const ll& showBit, const ll& Hier, const string& header,
         const string& space, const string& endline, const deque<E>& x) {
  cout << header << "(" << space;
  if (Hier) cout << endline;
  deque<E> que = x;
  while (!que.empty()) {
    E xx = que.front();
    que.pop_front();
    if (Hier) {
      if (Hier > 0) {
        out(showBit, Hier - 1, header + "  ", space, endline, xx);
      }
    } else {
      out(showBit, 0, "", space, "", xx);
    }
  }
  if (Hier) cout << header;
  cout << ")" << space;
  if (Hier) cout << endline;
};
template <typename E>
void out(const ll& showBit, const ll& Hier, const string& header,
         const string& space, const string& endline,
         const priority_queue<E>& x) {
  cout << header << "(" << space;
  if (Hier) cout << endline;
  priority_queue<E> que = x;
  while (!que.empty()) {
    E xx = que.top();
    que.pop();
    if (Hier) {
      if (Hier > 0) {
        out(showBit, Hier - 1, header + "  ", space, endline, xx);
      }
    } else {
      out(showBit, 0, "", space, "", xx);
    }
  }
  if (Hier) cout << header;
  cout << "]" << space;
  if (Hier) cout << endline;
};

template <typename T, typename... U>
void out(const ll& showBit, const ll& Hier, const string& header,
         const string& space, const string& endline, const T& x,
         const U&... y) {
  out(showBit, Hier, header, space, endline, x);
  out(showBit, Hier, header, space, endline, y...);
};

void zout() { cout << endl; };
template <int Hier = 0, int showBit = 0, typename... T>
void zout(const T&... x) {
  string endline = "\n";
  if (Hier == 0) endline = "";
  out(showBit, Hier, "", "  ", endline, x...);
  if (Hier == 0) 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, M;
  string S;
  cin >> N >> M >> S;
  ll Cnt = 0;
  rep(i, N) Cnt += (S[i] == '(');

  if ((2 * Cnt) != N) {
    yn(false);
    return 0;
  }
  if (S[0] == ')') {
    yn(false);
    return 0;
  }
  Cnt = 1;
  ll KK = 1;
  bool Zero = false;
  cnt(i, 1, N - 1) {
    if (S[i] == '(') {
      KK++;
      Cnt++;
    } else {
      KK--;
      if (S[i - 1] == '(') {
        Cnt++;
      }
    }
    Zero |= ((i < (N - 1)) && (KK == 0));
    if (KK < 0) {
      yn(false);
      return 0;
    }
  }

  yn(((Zero == 0) && (Cnt < M)) || ((Zero == 1) && (Cnt <= M)));
  if (((Zero == 0) && (Cnt < M)) || ((Zero == 1) && (Cnt <= M))) {
    cout << "(1+";

    cnt(i, 1, N - 1) {
      if (S[i] == '(') {
        if (S[i - 1] == ')') cout << '+';
        cout << "(1+";
      } else {
        if (S[i - 1] == '(') cout << "1";
        cout << ")";
      }
    }
    rep(i, M - Cnt) cout << "+1";
    cout << endl;
  }
  return 0;
}
yukicoder

結果

ソースコード
