#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
using namespace __gnu_pbds;
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
// find_by_order(k) returns iterator to kth element starting from 0;
// order_of_key(k) returns count of elements strictly smaller than k;
// useful defs
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vii;
typedef pair<ll, ll> pi;
typedef vector<pi> vpi;
typedef unordered_map<ll, ll> mll;
#define pb push_back
#define mp make_pair
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define per(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define trav(a, arr) for (auto &a : (arr))
#define sz(x) (int)(x).size()
#define mk_vec(name, sz, value) vi name(sz, value)
#define mk_mat(name, n, m, value) vii name(n, vi(m, value))
#define contains(x) find(x) != string::npos
#define tkv(vec, sz) rep(i, 0, sz) cin >> vec[i]
#define srv(vec) sort(vec.begin(), vec.end())
#define all(x) x.begin(), x.end()
#define less(a, b) a < b
#define vsum(vec) accumulate(vec.begin(), vec.end(), 0L);
#define vmax(vec) *max_element(vec.begin(), vec.end());
#define vmin(vec) *min_element(vec.begin(), vec.end());
#define pvc(vec) \
trav(x, vec) cout << x << " "; \
cout << endl;
#define put(x) cout << (x) << endl;
#define put2(x, y) cout << (x) << " " << (y) << endl;
#define put3(x, y, z) cout << (x) << " " << (y) << " " << (z) << endl;
#define mod(x) (x + MOD) % MOD
// debugging
#define timed(x) \
{ \
auto start = chrono::steady_clock::now(); \
x; \
auto end = chrono::steady_clock::now(); \
auto diff = end - start; \
cout << chrono::duration<double, milli>(diff).count() << " ms" << endl; \
}
void __print(int x)
{
cerr << x;
}
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template <typename T, typename V>
void __print(const pair<T, V> &x)
{
cerr << '{';
__print(x.first);
cerr << ',';
__print(x.second);
cerr << '}';
}
template <typename T>
void __print(const T &x)
{
int f = 0;
cerr << '{';
for (auto &i : x)
cerr << (f++ ? "," : ""), __print(i);
cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v)
{
__print(t);
if (sizeof...(v))
cerr << ", ";
_print(v...);
}
#ifndef ONLINE_JUDGE
#define debug(x...) \
cerr << "[" << #x << "] = ["; \
_print(x)
#else
#define debug(x...)
#endif
const ll MOD = 1e9 + 7;
const ll INF = 1e10 + 5;
// driver code
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
// freopen("input.in","r",stdin);
// freopen("output.out","w",stdout);
int T = 1;
// cin>>T;
while (T--)
{
int n, d, m;
cin >> n >> d >> m;
unordered_map<int, int> djobs;
unordered_map<int, vi> inds;
rep(i, 0, m)
{
int k;
cin >> k;
djobs[k]++;
inds[k].push_back(i);
}
vi *res = new vi[n + 1];
auto ok = [&](ll x, bool save = 0)
{
map<int, int> pq;
rep(t, 1, n + 1)
{
if (!pq.empty() && (*pq.begin()).first+d < t)
return 0;
if (djobs[t]) pq[t] = djobs[t];
int cur = x;
while (cur > 0 && !pq.empty())
{
auto it = pq.begin();
int mind = min(cur, (*it).second);
cur -= mind;
if (save)
{
assert(mind<=inds[(*it).first].size());
int k=mind;
while (k > 0)
{
res[t].push_back(inds[(*it).first].back());
inds[(*it).first].pop_back();
k--;
}
}
if ((*it).second - mind == 0) pq.erase(it);
else{ pq[(*it).first] = (*it).second - mind;}
}
}
return 1;
};
ll lo = 1, hi = m;
ll ans = 0;
while (lo <= hi)
{
ll mid = (lo + hi) / 2;
if (ok(mid))
{
hi = mid - 1;
ans = mid;
}
else
lo = mid + 1;
}
put(ans);
ok(ans, 1);
rep(i, 1, n + 1)
{
trav(j,res[i]){
cout << (j+1) << " ";
}
cout << "0" << endl;
}
}
return 0;
}
Compilation message
In file included from /usr/include/c++/10/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp:45,
from /usr/include/c++/10/ext/pb_ds/detail/container_base_dispatch.hpp:90,
from /usr/include/c++/10/ext/pb_ds/assoc_container.hpp:48,
from jobs.cpp:5:
jobs.cpp: In lambda function:
jobs.cpp:148:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
148 | assert(mind<=inds[(*it).first].size());
| ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
3920 KB |
Output is correct |
| 2 |
Correct |
22 ms |
3960 KB |
Output is correct |
| 3 |
Correct |
24 ms |
3880 KB |
Output is correct |
| 4 |
Correct |
23 ms |
3904 KB |
Output is correct |
| 5 |
Correct |
23 ms |
3920 KB |
Output is correct |
| 6 |
Correct |
23 ms |
3908 KB |
Output is correct |
| 7 |
Correct |
23 ms |
3960 KB |
Output is correct |
| 8 |
Correct |
25 ms |
3844 KB |
Output is correct |
| 9 |
Correct |
117 ms |
10148 KB |
Output is correct |
| 10 |
Correct |
119 ms |
10156 KB |
Output is correct |
| 11 |
Correct |
17 ms |
3540 KB |
Output is correct |
| 12 |
Correct |
30 ms |
6548 KB |
Output is correct |
| 13 |
Correct |
46 ms |
11936 KB |
Output is correct |
| 14 |
Correct |
104 ms |
16496 KB |
Output is correct |
| 15 |
Correct |
72 ms |
15252 KB |
Output is correct |
| 16 |
Correct |
136 ms |
20952 KB |
Output is correct |
| 17 |
Correct |
159 ms |
29968 KB |
Output is correct |
| 18 |
Correct |
124 ms |
26360 KB |
Output is correct |
| 19 |
Runtime error |
232 ms |
33152 KB |
Memory limit exceeded |
| 20 |
Correct |
169 ms |
30000 KB |
Output is correct |
