//#ifndef LOCAL
//#pragma GCC optimize ("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using indexed_multiset = tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update>;
#define int int64_t
#define vi vector
#define ss second
#define ff first
#define TESTCASES
#define all(x) (x).begin(), (x).end()
const int mod = 998244353;
const int MAXN=200000+5;
const int inf=1e18;
#ifndef khos
#define debug(...) 42
#endif
#define debug(args...) \
{ \
cout << "[" << #args << "]: "; \
my::debug::debug_out(args); \
cout << endl; \
}
namespace my::debug {
using std::cout;
template <typename T, typename = void>
struct is_container : std::false_type {};
template <typename T>
struct is_container<T, std::void_t<decltype(std::begin(std::declval<T>()))>>
: std::true_type {};
template <typename T>
constexpr bool is_container_v = is_container<T>::value;
template <typename Test, template <typename...> class Ref>
struct is_specialization : std::false_type {};
template <template <typename...> class Ref, typename... Args>
struct is_specialization<Ref<Args...>, Ref> : std::true_type {};
template <typename Test, template <typename...> class Ref>
constexpr bool is_specialization_v = is_specialization<Test, Ref>::value;
// https://stackoverflow.com/a/47563100
template <std::size_t N>
struct num {
static const constexpr auto value = N;
};
template <class F, std::size_t... Is>
void for_(F func, std::index_sequence<Is...>) {
(func(num<Is>{}), ...);
}
template <std::size_t N, typename F>
void for_(F func) {
for_(func, std::make_index_sequence<N>());
}
template <typename T>
constexpr auto is_coutable(int)
-> decltype(std::cout << std::declval<T>(), std::true_type{}) {
return std::true_type{};
}
template <typename T>
constexpr std::false_type is_coutable(...) {
return std::false_type{};
}
template <typename T>
constexpr bool is_coutable_v = decltype(is_coutable<T>(0))::value;
template <typename T>
void single_out(T x) {
if constexpr (std::is_same_v<T, std::string> | std::is_same_v<T, char*> ||
std::is_same_v<T, const char*>) {
cout << '"' << x << '"';
} else if constexpr (std::is_same_v<T, char>) {
cout << x;
} else if constexpr (std::is_integral_v<T> || std::is_floating_point_v<T> ||
std::is_enum_v<T> || std::is_pointer_v<T>) {
cout << x;
} else if constexpr (is_specialization_v<T, std::pair>) {
cout << "(";
single_out(x.first);
cout << ", ";
single_out(x.second);
cout << ")";
} else if constexpr (is_specialization_v<T, std::tuple>) {
cout << "(";
std::string sep = "";
for_<std::tuple_size_v<T>>([&](auto i) {
cout << exchange(sep, ", ");
single_out(std::get<i.value>(x));
});
cout << ")";
} else if constexpr (is_specialization_v<T, std::map> ||
is_specialization_v<T, std::unordered_map>) {
cout << "{";
std::string sep = "";
for (auto [k, v] : x) {
cout << exchange(sep, ", ");
single_out(k);
cout << ": ";
single_out(v);
}
cout << "}";
} else if constexpr (is_container_v<T>) {
if constexpr (is_specialization_v<T, std::vector>) {
cout << "[";
} else cout << "{";
std::string sep = "";
for (auto i : x) {
cout << exchange(sep, ", ");
single_out(i);
}
if constexpr (is_specialization_v<T, std::vector>) {
cout << "]";
} else cout << "}";
}
// types without iterator, f*** you, c++ comittee
else if constexpr (is_specialization_v<T, std::queue>) {
cout << "{";
std::string sep = "";
while (x.size()) {
cout << exchange(sep, ", ");
single_out(x.front());
x.pop();
}
cout << "}";
} else if constexpr (is_specialization_v<T, std::stack> ||
is_specialization_v<T, std::priority_queue>) {
std::vector<
std::remove_cv_t<std::remove_reference_t<decltype(x.top())>>>
v;
while (x.size()) {
v.push_back(x.top());
x.pop();
}
if constexpr (is_specialization_v<T, std::stack>)
std::reverse(v.begin(), v.end());
cout << "{";
std::string sep = "";
for (auto i : v) {
cout << exchange(sep, ", ");
single_out(i);
}
cout << "}";
}
// lastly, if the expression (cout << x) compiles, use it
else {
static_assert(is_coutable_v<T>, "The type given to debug() is not supported.");
cout << x;
}
}
template <typename T, typename... Rest>
void debug_out(T, Rest...);
void debug_out();
template <typename T, typename... Rest>
void debug_out(T x, Rest... rest) {
// single_out<std::remove_cv_t<std::decay_t<T>>>(x);
single_out<std::remove_cv_t<T>>(x);
if (sizeof...(rest) > 0) cout << ", ";
debug_out(rest...);
}
void debug_out() {
}
}; // namespace my::debug
void solution(){
int n,d,m;
cin >> n >> d >> m;
vi<int> a(m);
for(auto &x:a)cin >> x;
vi<pair<int,int>> p;
for(int i=0; i<m; i++){
p.push_back({a[i],i});
}
sort(all(p));
sort(all(a));
// debug(a);
int l=1,r=m;
while(l<r){
int mid=(l+r)/2;
int ind=0,ind2=0;
bool ok=1;
for(int i=1; i<=n; i++){
for(int j=ind2; j<min(ind2+mid,m); j++){
if(i<a[j])break;
else {
if(i-a[j]>d){
ok=0;
break;
}
}
ind++;
}
ind2=ind;
}
if(ok && ind>=m)r=mid;
else l=mid+1;
}
cout << r << '\n';
int ind=0,ind2=0;
for(int i=1; i<=n; i++){
vi<int> ans;
for(int j=ind2; j<min(ind2+r,m); j++){
if(i<a[j])break;
else {
ans.push_back(p[j].ss+1);
}
ind++;
}
ind2=ind;
ans.push_back(0);
for(auto x:ans)cout << x << ' ';
cout << '\n';
}
}
int32_t main(){
clock_t tStart = clock();
#ifdef khos
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int q = 1;
#ifdef TESTCASES
// cin >> q;
#endif
while(q--) {
solution();
cout << '\n';
}
cerr<<fixed<<setprecision(3)<<"\nTime Taken: "<<(double)(clock()- tStart)/CLOCKS_PER_SEC<<endl;
}
Compilation message (stderr)
jobs.cpp:28: warning: "debug" redefined
28 | #define debug(args...) \
|
jobs.cpp:25: note: this is the location of the previous definition
25 | #define debug(...) 42
|| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
