結果
| 問題 | No.3075 Mex Recurrence Formula |
| ユーザー |
 mihhiael
|
| 提出日時 | 2025-03-28 21:40:59 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 166 ms / 2,000 ms |
| コード長 | 7,175 bytes |
| コンパイル時間 | 2,097 ms |
| コンパイル使用メモリ | 162,980 KB |
| 実行使用メモリ | 12,800 KB |
| 最終ジャッジ日時 | 2025-03-28 21:41:07 |
| 合計ジャッジ時間 | 7,192 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 46 |
ソースコード
#include <cstdlib>#include <numeric>#if __has_include("all.h")#include "all.h"#else#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>#endif#include <atcoder/fenwicktree.hpp>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 autoauto &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)))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<convertible_to<ll> auto upper, class... Args>constexpr auto grid(Args... args) {if constexpr (ll(upper) < ll(1e7)) {return grid_seen(args...);} else {return grid_lite(args...);}}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 x;cin >> x;vell a(n);cin >> a;if(x <= n) {cout << a[x - 1] << lf;return;}fenwick_tree<ll> b(3e5), c(3e5);for(const auto &e:a) {if(e > ll(2.5e5)) cont;b.add(e, 1 - b.sum(e, e + 1));c.add(e, 1);}queue<ll> q;for(const auto &e:a) q.push(e);vell ans;ans.reserve(n + 1);times(n + 1) {ll ng = ll(2.5e5), ok = 0;while(abs(ng - ok) > 1) {const ll mid = midpoint(ng, ok);(b.sum(0, mid) == mid ? ok : ng) = mid;}b.add(ok, 1 - b.sum(ok, ok + 1));c.add(ok, 1);q.push(ok);ans.push_back(ok);const ll e = q.front(); q.pop();if(e > ll(2.5e5)) cont;c.add(e, -1);if(c.sum(e, e + 1) == 0) b.add(e, -1);}cout << ans[(x-1-n)%(n + 1)] << lf;}