結果
問題 |
No.3075 Mex Recurrence Formula
|
ユーザー |
|
提出日時 | 2025-03-28 21:25:12 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 324 ms / 2,000 ms |
コード長 | 1,438 bytes |
コンパイル時間 | 6,539 ms |
コンパイル使用メモリ | 332,596 KB |
実行使用メモリ | 16,460 KB |
最終ジャッジ日時 | 2025-03-28 21:25:43 |
合計ジャッジ時間 | 14,391 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
#include<bits/stdc++.h> #include<atcoder/all> #ifdef LOCAL #include <debug_print.hpp> #define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__) #else #define debug(...) (static_cast<void>(0)) #endif using namespace atcoder; using mint=modint1000000007; using namespace std; using ll=long long; using ul=unsigned long long; int dx[8] = {1, 0, -1, 0, -1, -1, 1, 1}; int dy[8] = {0, 1, 0, -1, -1, 1, -1, 1}; using Graph=vector<vector<int>>; int main(){ int N; ll X; cin>>N>>X; set<int>st; vector<int>C(N+1); for(int i=0;i<=N;i++)st.insert(i); queue<int>A; for(int i=0;i<N;i++){ int a; cin>>a; if(a<=N)C[a]++; A.push(a); st.erase(a); if(X-1==i){cout<<a<<endl;return 0;} } X-=N; vector<ll>ans; int mex=0; for(int i=0;i<=N;i++)if(C[i]==0){mex=i;break;} ans.push_back(mex); A.push(mex); C[mex]++; st.erase(mex); if(A.front()<=N){ C[A.front()]--; if(C[A.front()]==0)st.insert(A.front()); } A.pop(); while(true){ mex=*st.begin(); ans.push_back(mex); A.push(mex); C[mex]++; st.erase(mex); if(A.front()<=N){ C[A.front()]--; if(C[A.front()]==0)st.insert(A.front()); } A.pop(); if(ans[0]==ans.back()){ans.pop_back();break;} } cout<<ans[((X-1)%ans.size()+ans.size())%ans.size()]<<endl; }