Tutorial #

By adding $x$ or subtracting $x$, we can obtain any number in the same residue class so we only care about $a_i\bmod x$. 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 $1,2,3,4,\dots,x,1,2,3,4,\dots,x,\dots$. 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;
}