結果
問題 |
No.3075 Mex Recurrence Formula
|
ユーザー |
![]() |
提出日時 | 2025-03-28 21:32:56 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 166 ms / 2,000 ms |
コード長 | 897 bytes |
コンパイル時間 | 4,659 ms |
コンパイル使用メモリ | 257,644 KB |
実行使用メモリ | 16,000 KB |
最終ジャッジ日時 | 2025-03-28 21:33:06 |
合計ジャッジ時間 | 10,477 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
#include <stdio.h> #include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using mint = modint998244353; using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000000 #define Inf64 1000000000000000001LL int main(){ int n; long long x; cin>>n>>x; deque<long long> a(n); rep(i,n)cin>>a[i]; if(x<=n)cout<<a[x-1]<<endl; else{ vector<long long> cnt(n+5); rep(i,n){ if(a[i] < cnt.size())cnt[a[i]]++; } set<long long> noone; rep(i,cnt.size()){ if(cnt[i]==0)noone.insert(i); } x -= n; rep(i,n*2+5){ a.push_back(*noone.begin()); cnt[a.back()]++; noone.erase(noone.begin()); x--; if(x==0){ cout<<a.back()<<endl; return 0; } if(a[0]<cnt.size()){ cnt[a[0]]--; if(cnt[a[0]]==0)noone.insert(a[0]); } if(i!=n*2+4)a.pop_front(); } x--; cout<<a[x%(n+1)]<<endl; } return 0; }