Submission #681853

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
681853	2023-01-14T17:35:17 Z	peijar	Intercastellar (JOI22_ho_t1)	C++17	100 / 100	84 ms	9344 KB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;

string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
  bool first = true;
  string res = "[";
  for (const auto &x : v) {
    if (!first)
      res += ", ";
    first = false;
    res += to_string(x);
  }
  res += "]";
  return res;
}

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << to_string(H);
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int N;
  cin >> N;
  vector<pair<int, int>> elements;
  for (int i = 0; i < N; ++i) {
    int A;
    cin >> A;
    int cnt = 1;
    while (A % 2 == 0)
      cnt *= 2, A /= 2;
    if (!elements.empty())
      cnt += elements.back().first;
    elements.emplace_back(cnt, A);
    dbg(cnt);
  }

  int Q;
  cin >> Q;
  while (Q--) {
    int id;
    cin >> id;
    int pos = lower_bound(elements.begin(), elements.end(), pair(id, 0LL)) -
              elements.begin();
    cout << elements[pos].second << '\n';
  }
}

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	320 KB	Output is correct
3	Correct	31 ms	5080 KB	Output is correct
4	Correct	30 ms	2480 KB	Output is correct
5	Correct	53 ms	5624 KB	Output is correct
6	Correct	31 ms	5068 KB	Output is correct
7	Correct	53 ms	5592 KB	Output is correct
8	Correct	68 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	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	320 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	344 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	336 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	320 KB	Output is correct
3	Correct	31 ms	5080 KB	Output is correct
4	Correct	30 ms	2480 KB	Output is correct
5	Correct	53 ms	5624 KB	Output is correct
6	Correct	31 ms	5068 KB	Output is correct
7	Correct	53 ms	5592 KB	Output is correct
8	Correct	68 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	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	320 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	1 ms	344 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	1 ms	336 KB	Output is correct
23	Correct	32 ms	3156 KB	Output is correct
24	Correct	36 ms	6020 KB	Output is correct
25	Correct	75 ms	8888 KB	Output is correct
26	Correct	47 ms	5692 KB	Output is correct
27	Correct	43 ms	6012 KB	Output is correct
28	Correct	84 ms	9344 KB	Output is correct
29	Correct	81 ms	8820 KB	Output is correct
30	Correct	45 ms	3820 KB	Output is correct
31	Correct	80 ms	9272 KB	Output is correct