Submission #575101

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
575101	2022-06-09T16:58:58 Z	dariasc	Intercastellar (JOI22_ho_t1)	C++14	100 / 100	331 ms	9216 KB

Main

#include <bits/stdc++.h>
using namespace std;
 
#pragma region header
typedef long long ll;
template <typename Value>
using vec = vector<Value>;
istream &in = cin;
ostream &out = cout;
#define all(x) x.begin(), x.end()
#define fast() cin.tie(0); ios_base::sync_with_stdio(0)
#pragma endregion

void solve()
{
    int n; in >> n;
    vec<int> a(n);
    for (int i = 0; i < n; i++) {
        in >> a[i];
    }
    vec<int> sz(n);
    for (int i = 0; i < n; i++) {
        int c = 1;
        int x = a[i];
        while (x % 2 == 0) {
            x /= 2;
            c *= 2;
        }
        sz[i] = c;
    }
    vec<long long> pfx(n, 0);
    pfx[0] = sz[0];
    for (int i = 1; i < n; i++) {
        pfx[i] = sz[i] + pfx[i-1];
    }

    int q; in >> q;
    while (q--) {
        long long x; in >> x;
        int i = lower_bound(all(pfx), x) - pfx.begin();
        
        int o = a[i];
        while (o % 2 == 0) {
            o /= 2;
        }
        out << o << endl;
    }
}

int main()
{
    fast();
    solve(); return 0;
    int t; in >> t;
    while (t--) {
        solve();
    }
}

Compilation message

Main.cpp:4: warning: ignoring '#pragma region header' [-Wunknown-pragmas]
    4 | #pragma region header
      | 
Main.cpp:12: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
   12 | #pragma endregion
      |

Subtask #1

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	320 KB	Output is correct
3	Correct	64 ms	4012 KB	Output is correct
4	Correct	205 ms	2256 KB	Output is correct
5	Correct	296 ms	5452 KB	Output is correct
6	Correct	137 ms	3984 KB	Output is correct
7	Correct	287 ms	5580 KB	Output is correct
8	Correct	318 ms	5668 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	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	2 ms	340 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	2 ms	328 KB	Output is correct
12	Correct	2 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	2 ms	332 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	0 ms	320 KB	Output is correct
3	Correct	64 ms	4012 KB	Output is correct
4	Correct	205 ms	2256 KB	Output is correct
5	Correct	296 ms	5452 KB	Output is correct
6	Correct	137 ms	3984 KB	Output is correct
7	Correct	287 ms	5580 KB	Output is correct
8	Correct	318 ms	5668 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	2 ms	340 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	2 ms	328 KB	Output is correct
20	Correct	2 ms	340 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	2 ms	332 KB	Output is correct
23	Correct	175 ms	3028 KB	Output is correct
24	Correct	128 ms	5292 KB	Output is correct
25	Correct	298 ms	8804 KB	Output is correct
26	Correct	172 ms	5556 KB	Output is correct
27	Correct	143 ms	5476 KB	Output is correct
28	Correct	312 ms	9216 KB	Output is correct
29	Correct	331 ms	8704 KB	Output is correct
30	Correct	225 ms	3688 KB	Output is correct
31	Correct	316 ms	9160 KB	Output is correct