Submission #1242849

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242849		repeat21	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	87 ms	18760 KiB

jobs

#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <set>
#include <cassert>
#include <queue>
#include <unordered_map>
#include <iomanip>
#include <map>
#include <climits>

int f(int x) {
  return x & (x + 1);
}

int g(int x) {
  return x | (x + 1);
}


struct Fenwick {
  std::vector<int> values;
  std::vector<int> fenwick;
  Fenwick(const std::vector<int>& vals) : values(vals) {
    std::sort(values.begin(), values.end());
    values.erase(std::unique(values.begin(), values.end()), values.end());
    fenwick.assign(values.size(), 0);
  }

  int GetIndex(int x) {
    return std::distance(values.begin(), std::lower_bound(values.begin(), values.end(), x));
  }

  void Update(int x) {
    for (int i = GetIndex(x); i < fenwick.size(); i = g(i)) {
      fenwick[i]++;
    }
  }

  int GetPref(int ind) {
    int res = 0;
    for (int i = ind; i >= 0; i = f(i) - 1) {
      res += fenwick[i];
    }
    return res;
  }

  int GetSum(int l, int r) {
    return GetPref(GetIndex(r)) - GetPref(GetIndex(l) - 1);
  }
};

using ll = long long;
using ld = long double;

bool cmp1(std::pair<int, int> p1, std::pair<int, int> p2) {
  if (p1.second != p2.second) {
    return p1.second < p2.second;
  }
  return p1.first > p2.first;
}

bool cmp2(std::pair<int, int> p1, std::pair<int, int> p2) {
  if (p1.first != p2.first) {
    return p1.first < p2.first;
  }
  return p1.second > p2.second;
}

struct PairHash {
  template <class T1, class T2>
  std::size_t operator() (const std::pair<T1, T2> &p) const {
    auto h1 = std::hash<T1>{}(p.first);
    auto h2 = std::hash<T2>{}(p.second);

    return h1 ^ (h2 << 1);
  }
};

std::unordered_map<std::pair<int, int>, std::pair<int, int>, PairHash> prevv;
std::map<std::pair<int, int>, std::pair<int, int>> prev;

char get_move(std::pair<int, int> from, std::pair<int, int> to) {
  if (to.first == from.first + 1) {
    return 'D';
  }
  if (to.first == from.first - 1) {
    return 'U';
  }
  if (to.second == from.second + 1) {
    return 'R';
  }
  if (to.second == from.second - 1) {
    return 'L';
  }
}

long long gcd(long long a, long long b) {
  while (b) {
    a %= b;
    std::swap(a, b);
  }
  return std::abs(a);
}

long long lcm(long long a, long long b) {
  if (a == 0 || b == 0) {
    return 0;
  }
  return std::abs(a / gcd(a, b)) * b;
}

const int mx_value = 1e9;

struct Edge {
  ll to;
  ll c;
  Edge(ll to, ll c) : to(to), c(c) {}
};

template <typename T>
using MinHeap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

ll n, d, m;
std::vector<ll> cnt;
std::vector<std::vector<ll>> by_days;

bool check(int robots) {
  MinHeap<std::pair<int, int>> todo;
  for (int i = 1; i <= n; ++i) {
    todo.emplace(i, cnt[i]);
    int r = robots;
    while (!todo.empty() && r >= todo.top().second) {
      r -= todo.top().second;
      todo.pop();
    }
    if (!todo.empty()) {
      auto [ind, val] = todo.top();
      if (ind + d <= i) {
        return false;
      }
      todo.pop();
      todo.emplace(ind, val - r);
    }
  }
  return true;
}

void do_work(int robots) {
  MinHeap<std::pair<int, int>> todo;
  for (int i = 1; i <= n; ++i) {
    todo.emplace(i, cnt[i]);
    int r = robots;
    while (!todo.empty() && r >= todo.top().second) {
      auto [day, val] = todo.top();
      r -= val;
      for (int x : by_days[day]) {
        std::cout << x << ' ';
      }
      todo.pop();
    }
    if (!todo.empty()) {
      auto [day, val] = todo.top();
      todo.pop();
      for (int i = 0; i < r; ++i) {
        std::cout << by_days[day].back() << ' ';
        by_days[day].pop_back();
      }
      todo.emplace(day, val - r);
    }
    std::cout << 0 << '\n';
  }
}


int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);

  std::cin >> n >> d >> m;
  cnt.resize(n + 1);
  by_days.resize(n + 1);
  for (int i = 1; i <= m; ++i) {
    int day;
    std::cin >> day;
    cnt[day]++;
    by_days[day].push_back(i);
  }

  int low = 0;
  int high = 1e6 + 1;
  while (low + 1 < high) {
    int mid = (low + high) / 2;
    if (check(mid)) {
      high = mid;
    } else {
      low = mid;
    }
  }
  std::cout << high << '\n';
  do_work(high);
}

Compilation message (stderr)

jobs.cpp: In function 'char get_move(std::pair<int, int>, std::pair<int, int>)':
jobs.cpp:97:1: warning: control reaches end of non-void function [-Wreturn-type]
   97 | }
      | ^

• Subtask 1: 100 / 100