Competitive Programming Solutions

1466B - Last Minute Enhancements

30 Dec 2020 — Tags: greedy — URL

From start to end, increase element if it has already been encountered before (remember elements are given in non-decreasing order). Then, count unique elements.

Time complexity: $O(n)$

Memory complexity: $O(n)$

Click to show code.

 

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int solve(vi a)
{
    int n = (int)(a).size();
    vector<bool> vis(a.back() + 5, false);
    for (int i = 0; i < n; ++i)
    {
        if (vis[a[i]])
            a[i]++;
        vis[a[i]] = true;
    }
    return distance(begin(a), unique(begin(a), end(a)));
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vi a(n);
        for (auto &x : a)
            cin >> x;
        cout << solve(a) << endl;
    }
    return 0;
}

Related posts