Codeforces Round #830 (Div. 2) D1. Balance (Easy version)

Codeforces Round #830 (Div. 2) D1. Balance (Easy version)

Let’s look at a stupid solution and try to improve it.

In a stupid solution, we can simply add to the set, and when answering a query, iterate over the numbers $0,k,2k,3k$,… and so on until we find the answer. This solution will take a long time if the answer is $c\cdot k$, where c is large.

We will improve the solution. If a request comes to us for the first time for a given $k$, then we calculate the answer for it greedily and remember it. In the future, we will no longer check with 0 whether there is a number in the set, but with the previous answer.

Let’s count for each value x how many times we can check for its presence in the set. First, we do this for k such that x is divisible by k. Secondly, the set must already contain elements $0,k,2k,\dots ,x-k$, that is, $\frac{x}{k}$ numbers. Note that if $k$ is not one of the largest divisors of x, then $\frac{x}{k}$ becomes greater than $q$. Therefore, this solution will work quite quickly.

#include
using namespace std;

typedef long long LL;

int main()
{
    set<LL> S;
    map<LL,LL> f;

    int q;cin>>q;
    while(q--)
    {
        char op[2];LL x;cin>>op>>x;
        if(*op=='+') S.insert(x);
        if(*op=='?')
        {
            if(!f.count(x)) f[x]=1;
            while(S.count(f[x]*x))
                f[x]++;
            cout<<f[x]*x<<endl;
        }
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26