Submission #1158277

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158277		Doncho_Bonboncho	OGLEDALA (COI15_ogledala)	C++20	100 / 100	1794 ms	198344 KiB

ogledala

#include <algorithm>
#include <cassert>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

typedef long long llint;
typedef std::pair<llint, llint> par;

const int MAXN = 100100;

struct Gap {
  llint len, cnt;
  int i;
};

llint a[MAXN];
llint b[MAXN];

std::vector<par> V;

void split(llint len) {
  V.clear();
  if(len == 0) return;
  V.push_back({len+1, 0});
  V.push_back({len, 1});
  for(int i = 0; i < (int)V.size(); i += 2) {
    assert(V[i].first == V[i+1].first + 1);
    llint next_len1 = V[i].first / 2, next_cnt1 = V[i].second;
    llint next_len2 = (V[i+1].first - 1) / 2, next_cnt2 = V[i+1].second;
    V[i+1].first / 2 == next_len1 ? next_cnt1 += V[i+1].second : next_cnt2 += V[i+1].second;
    (V[i].first - 1) / 2 == next_len1 ? next_cnt1 += V[i].second : next_cnt2 += V[i].second;
    if(next_len1 == 0 && next_len2 == 0) break;
    V.push_back({next_len1, next_cnt1});
    V.push_back({next_len2, next_cnt2});
  }
  while(!V.empty() && V.back().first == 0) V.pop_back();
  llint cnt1 = 0;
  while(!V.empty() && V.back().first == 1) {
    cnt1 += V.back().second;
    V.pop_back();
  }
  if(cnt1 > 0) V.push_back({1, cnt1});
}

llint query(int i, llint need_len, llint need_ind) {
  llint pos = a[i] + 1;
  llint len = a[i+1] - a[i] - 1;
  while(len > need_len) {
    split((len - 1) / 2);
    llint cnt = 0;
    for(auto &p : V)
      if(p.first == need_len) cnt += p.second;
    if(cnt >= need_ind) {
      len = (len - 1) / 2;
    } else {
      pos += 1 + (len - 1) / 2;
      len = len / 2;
      need_ind -= cnt;
    }
  }
  assert(len == need_len);
  return pos + (len - 1) / 2;
}

int main(void) {
  llint m;
  int n, k;
  std::cin >> m >> n >> k;
  for(int i = 1; i <= n; ++i)
    std::cin >> a[i];
  a[0] = 0;
  a[n+1] = m + 1;
  static std::vector<Gap> gaps;
  for(int i = 0; i <= n; ++i) {
    split(a[i+1] - a[i] - 1);
    for(auto &p : V)
      if(p.first > 0 && p.second > 0)
        gaps.push_back({p.first, p.second, i});
  }
  std::sort(gaps.begin(), gaps.end(), [] (const Gap &x, const Gap &y) {
      if(x.len != y.len) return x.len > y.len;
      return x.i < y.i;
    }
  );
  for(int i = 0; i < k; ++i)
    std::cin >> b[i];
  int curq = 0;
  while(curq < k && b[curq] <= n) {
    std::cout << a[b[curq]] << std::endl;
    curq++;
  }
  llint cur = n + 1;
  for(auto &g : gaps) {
    while(curq < k && b[curq] < cur + g.cnt) {
      std::cout << query(g.i, g.len, b[curq] - cur + 1) << std::endl;
      curq++;
    }
    cur += g.cnt;
  }
  return 0;
}

• Subtask 1: 19 / 19
• Subtask 2: 22 / 22
• Subtask 3: 59 / 59