結果
問題 | No.3135 AAABC |
ユーザー |
|
提出日時 | 2025-05-02 21:59:14 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 20 ms / 2,000 ms |
コード長 | 6,734 bytes |
コンパイル時間 | 1,474 ms |
コンパイル使用メモリ | 157,068 KB |
実行使用メモリ | 6,272 KB |
最終ジャッジ日時 | 2025-05-02 21:59:18 |
合計ジャッジ時間 | 2,508 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
ソースコード
#if __has_include("all.h") #include "all.h" #else // necessary for snippet #include <algorithm> #include <concepts> #include <cstdint> #include <ios> #include <iostream> #include <istream> #include <limits> #include <ostream> #include <queue> #include <random> #include <ranges> #include <set> #include <stdexcept> #include <string> #include <type_traits> #include <utility> #include <vector> #include <atcoder/modint.hpp> // often use #include <map> #endif inline namespace { using namespace std; using ll = long long; using pall = pair<ll, ll>; template<class T> using vec = vector<T>; template<class T> using veve = vec<vec<T>>; using vell = vec<ll>; using vest = vec<string>; using vebo = basic_string<bool>; using vevell = veve<ll>; template<class T> using mset = multiset<T>; template<class T> using priority_queue_ascend = priority_queue<T, vec<T>, decltype([](const T a, const T b) { return a > b; })>; const ll inf = numeric_limits<ll>::max(); const string sp = " "; const string lf = "\n"; const auto &npos = string::npos; const vec<pall> grid_move4 = { {0, 1}, {-1, 0}, {0, -1}, {1, 0} }; const vec<pall> grid_move8 = [] { auto ret = grid_move4; ret.insert(ret.end(), { {-1, 1}, {-1, -1}, {1, -1}, {1, 1} }); return ret; }(); constexpr ll MOD = 998244353; // constexpr ll MOD = 1e9 + 7; #define cont continue #define br break #define auot auto #define whlie while auto &ciN = cin; auto &icn = cin; auto &icN = cin; constexpr bool ture = true; using namespace atcoder; using mint = static_modint<MOD>; #define times(N) static_assert(is_integral_v<decltype((N) + 0)>, "times(): N must be integral"); for(typedef decltype((N) + 0) _int; [[maybe_unused]] const _int _i: views::iota((_int)0, (N))) #define tiems times #define itmes times template<int M> istream &operator>>(istream &in, static_modint<M> &i) { intmax_t tmp; in >> tmp; i = tmp; return in; } template<int M> ostream &operator<<(ostream &out, const static_modint<M> &i) { return out << i.val(); } template<class T, class U> istream &operator>>(istream &in, pair<T, U> &p) { return in >> p.first >> p.second; } template<class T, class U> ostream &operator<<(ostream &out, const pair<T, U> &p) { return out << p.first << sp << p.second; } template<class T> istream &operator>>(istream &in, vec<T> &v) { for(auto &&e: v) { in >> e; } return in; } namespace myinput { template<class... Ts> istream &in(Ts&... vecs) { static_assert(sizeof...(vecs) != 0, "myfunc::in(): At least one vector must be provided"); const set sizes = { vecs.size()... }; if(sizes.size() > 1) { throw invalid_argument("myfunc::in(): All vectors must have the same size"); } times(*sizes.begin()) { ((cin >> vecs[_i]), ...); } return cin; } } using myinput::in; ostream &out(const ranges::range auto &v, const string &delim, ostream &out = cout) { for(const auto &e: v) { out << e << delim; } return out; } [[nodiscard]] const string &yesno(const bool cond, const string &yes = "Yes", const string &no = "No") noexcept { if(cond) return yes; return no; } // [mi, ma) [[nodiscard]] uint64_t randint(const uint64_t mi, const uint64_t ma) noexcept { static random_device seed; static mt19937_64 mt(seed()); if(mi > ma) [[unlikely]] return randint(ma, mi); if(mi == ma) [[unlikely]] return mi; const uint64_t w = ma - mi; uint64_t r; do { r = mt(); } while(mt.max() - mt.max() % w <= r); return r % w + mi; } template<class T, class U> requires common_with<T, U> [[nodiscard]] constexpr auto min(T &&a, U &&b) noexcept { return std::min<common_type_t<T, U>>(std::forward<T>(a), std::forward<U>(b)); } template<class T, class U> requires common_with<T, U> [[nodiscard]] constexpr auto max(T &&a, U &&b) noexcept { return std::max<common_type_t<T, U>>(std::forward<T>(a), std::forward<U>(b)); } template<class T> [[nodiscard]] const T &min(const vec<T> &v) { return *ranges::min_element(v); } template<class T> [[nodiscard]] const T &max(const vec<T> &v) { return *ranges::max_element(v); } template<class... Args> [[nodiscard]] auto reduce(const ranges::range auto &v, Args... args) { return reduce(v.begin(), v.end(), args...); } [[nodiscard]] constexpr ll powll(ll a, ll b, const ll m = inf) { if(b < 0) [[unlikely]] throw invalid_argument("powll(): exponent less than zero"); if(m < 1) [[unlikely]] throw invalid_argument("powll(): modulo less than one"); a %= m; ll ret = 1; while(b) { if(b % 2) ret *= a, ret %= m; a *= a, a %= m; b /= 2; } return ret; } template<class T, class U> requires assignable_from<T&, U> && totally_ordered_with<T, U> bool mini(T &var, U &&val) noexcept { const bool cmp = var > val; if(cmp) var = val; return cmp; } template<class T, class U> requires assignable_from<T&, U> && totally_ordered_with<T, U> bool maxi(T &var, U &&val) noexcept { const bool cmp = var < val; if(cmp) var = val; return cmp; } namespace myclass { class [[nodiscard]] grid_base { public: grid_base(const ll h, const ll w) noexcept : height(h), width(w) {} [[nodiscard]] ll operator()(const ll i, const ll j) const noexcept { if(!isvalid(i, j)) return -1; return i * width + j; } [[nodiscard]] ll operator()(const pall &p) const noexcept { return (*this)(p.first, p.second); } protected: bool isvalid(const ll i, const ll j) const noexcept { return 0 <= i && 0 <= j && i < height && j < width; } const ll height, width; }; class [[nodiscard]] grid_seen : public myclass::grid_base { public: grid_seen(const ll h, const ll w) : grid_base(h, w) { visited = vebo(h * w, false); } [[nodiscard]] bool &seen(const ll i, const ll j) & { if(!isvalid(i, j)) [[unlikely]] throw out_of_range("grid::seen(): out of range"); return visited[i * width + j]; } [[nodiscard]] bool &seen(const pall &p) & { return seen(p.first, p.second); } private: vebo visited; }; } using grid_lite = myclass::grid_base; using myclass::grid_seen; template<class T> auto erase_single(mset<T> &mset, T &&v) { const auto it = mset.find(v); if(it == mset.end()) [[unlikely]] throw invalid_argument("erase_single(): why v not in mset!?!?"); return mset.erase(it); } } void solve(); int main(void) { cin.tie(nullptr); ios::sync_with_stdio(false); solve(); return 0; } void solve() { ll n ; cin >> n; ll s; cin >> s; string ans; ll cnt = 0; for(intmax_t i=0;i<intmax_t(powll(3, n));i++) { ll c[3]{}; ll tmp = i; for(intmax_t j=0;j<intmax_t(n);j++) { c[tmp % 3]++; tmp /= 3; } if(c[0] && c[1] && c[2]) { cnt++; } if(cnt == s) { tmp = i; times(n) { ans += 'A' + tmp % 3; tmp /= 3; } ranges::reverse(ans); br; } } if(cnt < s) { cout << -1 << lf; return; } cout << ans << lf; }