Submission #538650

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
538650	2022-03-17T11:17:54 Z	emsilverfox	Intercastellar (JOI22_ho_t1)	C++14	100 / 100	470 ms	5328 KB

Main

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

ll fun(ll brojic)
{
    while (brojic % 2 == 0)
        brojic /= 2;

    return brojic;
}

ll pow2(int n)
{
    ll pov = 1;
    while (n--) pov *= 2;
    return pov;
}

ll funner(ll brojic)
{
    int ret = 0;
    while (brojic % 2 == 0)
    {
        ret++;
        brojic /= 2;
    }
    return pow2(ret);
}

int main()
{
    int n;
    cin >> n;
    
    vector<ll> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];

    vector<ll> csum(n);
    csum[0] = funner(a[0]);
    for (int i = 1; i < n; i++) {
        csum[i] = csum[i - 1] + funner(a[i]);
    }

    int q;
    cin >> q;
    for (int i = 0; i < q; i++)
    {
        ll x;
        cin >> x;

        int pos = lower_bound(csum.begin(), csum.end(), x) - csum.begin();
        cout << fun(a[pos]) << endl;
    }
    
    return 0;
}

Subtask #1

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	89 ms	3376 KB	Output is correct
4	Correct	262 ms	1232 KB	Output is correct
5	Correct	384 ms	3700 KB	Output is correct
6	Correct	180 ms	3004 KB	Output is correct
7	Correct	347 ms	3708 KB	Output is correct
8	Correct	369 ms	3824 KB	Output is correct

Subtask #2

35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	2 ms	212 KB	Output is correct
8	Correct	3 ms	212 KB	Output is correct
9	Correct	2 ms	224 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	3 ms	212 KB	Output is correct
12	Correct	3 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	3 ms	212 KB	Output is correct

Subtask #3

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	89 ms	3376 KB	Output is correct
4	Correct	262 ms	1232 KB	Output is correct
5	Correct	384 ms	3700 KB	Output is correct
6	Correct	180 ms	3004 KB	Output is correct
7	Correct	347 ms	3708 KB	Output is correct
8	Correct	369 ms	3824 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	2 ms	212 KB	Output is correct
16	Correct	3 ms	212 KB	Output is correct
17	Correct	2 ms	224 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	3 ms	212 KB	Output is correct
20	Correct	3 ms	212 KB	Output is correct
21	Correct	1 ms	212 KB	Output is correct
22	Correct	3 ms	212 KB	Output is correct
23	Correct	204 ms	1960 KB	Output is correct
24	Correct	211 ms	3344 KB	Output is correct
25	Correct	405 ms	5328 KB	Output is correct
26	Correct	261 ms	2796 KB	Output is correct
27	Correct	221 ms	2944 KB	Output is correct
28	Correct	466 ms	4548 KB	Output is correct
29	Correct	470 ms	3772 KB	Output is correct
30	Correct	312 ms	1268 KB	Output is correct
31	Correct	464 ms	4296 KB	Output is correct