Tutorial #
By adding or subtracting , we can obtain any number in the same residue class so we only care about . To maximize the mex, we need to obtain consecutive numbers starting from 0 as many as possible. In the perspective of modular, that means we need . Therefore, we should store the size of each residue class and try to increase the answer when we have a new number.
Code #
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q,x;
cin>>q>>x;
vector<int> cnt(x);
int ans=0;
while(q--){
int n;
cin>>n;
cnt[n%x]++;
while(cnt[ans%x]){
cnt[ans%x]--;
ans++;
}
cout<<ans<<endl;
}
return 0;
}