Submission #1215027

#TimeUsernameProblemLanguageResultExecution timeMemory
1215027zfs732OGLEDALA (COI15_ogledala)C++20
0 / 100
4099 ms180064 KiB
/* * _|_|_|_|_| _|_|_|_| _|_|_| _|_|_|_|_| _|_|_| _|_| * _| _| _| _| _| _| _| * _| _|_|_| _|_| _| _|_| _| * _| _| _| _| _| _| * _|_|_|_|_| _| _|_|_| _| _|_|_| _|_|_|_| */ #include <bits/stdc++.h> auto Split(long long len) { std::vector<std::pair<long long, long long>> gt; if (len == 0) { return gt; } gt.emplace_back(len + 1, 0); gt.emplace_back(len, 1); for (int i = 0; i < gt.size(); i += 2) { long long nlen1 = gt[i].first / 2, ncnt1 = gt[i].second; long long nlen2 = (gt[i + 1].first - 1) / 2, ncnt2 = gt[i + 1].second; if ((gt[i].first - 1) / 2 == nlen1) { ncnt1 += gt[i].second; } else { ncnt2 += gt[i].second; } if (gt[i + 1].first / 2 == nlen1) { ncnt1 += gt[i + 1].second; } else { ncnt2 += gt[i + 1].second; } if (!nlen1 && !nlen2) { break; } gt.emplace_back(nlen1, ncnt1); gt.emplace_back(nlen2, ncnt2); } for (; !gt.empty() && gt.back().first == 0; gt.pop_back()) {} long long cnt1 = 0; for (; !gt.empty() && gt.back().first == 1; gt.pop_back()) { cnt1 += gt.back().second; } if (cnt1) { gt.emplace_back(1, cnt1); } return gt; } int main() { freopen("seat.in", "r", stdin); freopen("seat.out", "w", stdout); freopen("seat.err", "w", stderr); std::ios::sync_with_stdio(false); std::cin.tie(nullptr); long long M; int N, Q; std::cin >> M >> N >> Q; std::vector<long long> A(N), C{-1, M}, ans(Q); std::vector<std::tuple<long long, int, long long>> arr; std::vector<std::pair<long long, int>> qur; for (auto &v: A) { std::cin >> v, v--, C.emplace_back(v); } std::ranges::sort(C); for (int i = 1; i <= N + 1; i++) { if (C[i - 1] != C[i]) { auto pt = Split(C[i] - C[i - 1] - 1); for (auto [len, cnt]: pt) { if (cnt) { arr.emplace_back(-len, i, cnt); } } } } std::ranges::sort(arr); for (int i = 0; i < Q; i++) { long long x; std::cin >> x, x--; qur.emplace_back(x, i); } std::ranges::sort(qur); for (auto [len, id, cnt]: arr) { std::cerr << len << ' ' << cnt << ' ' << id << '\n'; } long long ti = N; auto it = arr.begin(); for (auto [x, id]: qur) { while (it != arr.end() && ti + std::get<2>(*it) <= x) { ti += std::get<2>(*it++); } if (x < N) { ans[id] = A[x]; } else { auto [len, tid, cnt] = *it; len = -len, x -= ti; long long tlen = C[tid] - C[tid - 1] - 1, st = C[tid - 1] + 1; while (tlen != len) { auto pt = Split((tlen - 1) / 2); bool ok = false; for (auto [nlen, ncnt]: pt) { if (nlen == len) { if (ncnt > x) { ok = true; } else { x -= ncnt; } break; } } if (!ok) { st += (tlen + 1) / 2; tlen = tlen / 2; } else { tlen = (tlen - 1) / 2; } } ans[id] = st + (len - 1) / 2; } } for (auto v: ans) { std::cout << v + 1 << '\n'; } return 0; }

Compilation message (stderr)

ogledala.cpp: In function 'int main()':
ogledala.cpp:46:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |   freopen("seat.in", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
ogledala.cpp:47:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |   freopen("seat.out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
ogledala.cpp:48:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |   freopen("seat.err", "w", stderr);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...