#include <bits/stdc++.h>
#include <cmath>
#include <cstdlib>
#include <ctime>
#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 orderedMultiset = tree<T ,null_type,std::less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
#define f first
#define s second
#define pb push_back
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) (x).begin(), (x).end()
ll MOD = 1000000007;
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
ll add(ll x, ll y)
{
x += y;
while(x >= MOD) x -= MOD;
while(x < 0) x += MOD;
return x;
}
ll mult(ll x, ll y)
{
return (x * 1ll * y) % MOD;
}
ll lpow(ll x, ll y)
{
if(y == 0){
return 1;
}
ll z = 1;
while(y)
{
if(y & 1) z = mult(z, x);
x = mult(x, x);
y >>= 1;
}
return z;
}
bool prime(int x)
{
for(int i = 2; i * 1ll * i <= x; i++)
if(x % i == 0)
return false;
return true;
}
ll inv(ll x) {
return lpow(x, MOD - 2);
}
ll divide(ll x, ll y)
{
return mult(x, inv(y));
}
long long gcd(long long int a, long long int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to return LCM of two numbers
long long lcm(int a, int b)
{
return (a / gcd(a, b)) * b;
}
//math
vector <ll> ar;
vector <ll> br;
void printDivisors(ll n)
{
// Note that this loop runs till square root
for (ll i=1; i<=sqrt(n); i++)
{
if (n%i == 0)
{
// If divisors are equal, print only one
if (n/i == i){
ar.pb(i);
}
else{
ar.pb(i);
ar.pb(n/i);
} // Otherwise print both
}
}
}
void bprintDivisors(ll n)
{
// Note that this loop runs till square root
for (ll i=1; i<=sqrt(n); i++)
{
if (n%i == 0)
{
// If divisors are equal, print only one
if (n/i == i){
br.pb(i);
}
else{
br.pb(i);
br.pb(n/i);
} // Otherwise print both
}
}
}
struct DSU {
vector<int> e;
DSU(int N) { e = vector<int>(N, -1); }
// get representive component (uses path compression)
int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
bool same_set(int a, int b) { return get(a) == get(b); }
int size(int x) { return -e[get(x)]; }
bool unite(int x, int y) { // union by size
x = get(x), y = get(y);
if (x == y) return false;
if (e[x] > e[y]) swap(x, y);
e[x] += e[y]; e[y] = x; return true;
}
};
/** Computes x^n modulo m in O(log p) time. */
ll qexp(ll a, ll b, ll m) {
ll res = 1;
while (b) {
if (b % 2) res = res * a % m;
a = a * a % m;
b /= 2;
}
return res;
}
vector<ll> fact, invf;
void precompute(int n) {
/** Precomputes n! from 0 to MAXN. */
fact.assign(n + 1, 1);
for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % MOD;
invf.assign(n + 1, 1);
/**
* Precomputes all modular inverse factorials
* from 0 to MAXN in O(n + log p) time
*/
invf[n] = qexp(fact[n], MOD - 2, MOD);
for (int i = n - 1; i > 0; i--) invf[i] = invf[i + 1] * (i + 1) % MOD;
}
/** Computes nCr mod p */
ll nCk(ll n,ll k) {
if (k < 0 || k > n) return 0;
return fact[n] * invf[k] % MOD * invf[n - k] % MOD;
// return fact[n] * qexp(fact[k], MOD - 2, MOD) % MOD * qexp(fact[n - k], MOD - 2, MOD) % MOD;
}
void solve(){
int n,d,m;cin>>n>>d>>m;
vector <pi> v;
rep(i,0,m){
int u;cin>>u;v.pb({u,i});
}
sort(v.begin(),v.end());
int lo = 0; int hi = 1000000005;
hi++;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
int day = 1;
int cnt = 0;
bool yn = true;
rep(i,0,m){
if(cnt == mid){
// reset
day++;
cnt = 0;
}
if(v[i].first > day){
day = v[i].first;
cnt = 0;
}
if(day - v[i].first > d){ // past expiration
yn = false;
}
cnt++;
}
if (yn) {
hi = mid;
} else {
lo = mid + 1;
}
}
int day = 0;
int cnt = 0;
bool yn = true;
vi aj[n]; // for every day
rep(i,0,m){
if(cnt == hi){
// reset
day++;
cnt = 0;
}
if(v[i].first > day){
day = v[i].first-1; // adjust for 0 indexed
cnt = 0;
}
aj[day].pb(v[i].second);
cnt++;
}
cout<<hi<<endl;
rep(i,0,n){
rep(j,0,aj[i].size()){
cout<<aj[i][j]+1<<" ";
}
cout<<0<<endl;
}
}
int main(){
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;t=1;
while(t--){
solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
Compilation message
jobs.cpp: In function 'void solve()':
jobs.cpp:17:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | #define rep(i, a, b) for(int i = a; i < (b); ++i)
| ^
jobs.cpp:233:9: note: in expansion of macro 'rep'
233 | rep(j,0,aj[i].size()){
| ^~~
jobs.cpp:216:10: warning: unused variable 'yn' [-Wunused-variable]
216 | bool yn = true;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
3276 KB |
Output is correct |
| 2 |
Correct |
28 ms |
3288 KB |
Output is correct |
| 3 |
Correct |
28 ms |
3288 KB |
Output is correct |
| 4 |
Correct |
38 ms |
3288 KB |
Output is correct |
| 5 |
Correct |
34 ms |
3280 KB |
Output is correct |
| 6 |
Correct |
28 ms |
3288 KB |
Output is correct |
| 7 |
Correct |
28 ms |
3288 KB |
Output is correct |
| 8 |
Correct |
28 ms |
3288 KB |
Output is correct |
| 9 |
Correct |
136 ms |
5072 KB |
Output is correct |
| 10 |
Correct |
140 ms |
5328 KB |
Output is correct |
| 11 |
Correct |
25 ms |
2608 KB |
Output is correct |
| 12 |
Correct |
48 ms |
4808 KB |
Output is correct |
| 13 |
Correct |
71 ms |
8636 KB |
Output is correct |
| 14 |
Correct |
114 ms |
11408 KB |
Output is correct |
| 15 |
Correct |
117 ms |
11832 KB |
Output is correct |
| 16 |
Correct |
164 ms |
16100 KB |
Output is correct |
| 17 |
Correct |
203 ms |
20156 KB |
Output is correct |
| 18 |
Correct |
210 ms |
19764 KB |
Output is correct |
| 19 |
Correct |
322 ms |
23300 KB |
Output is correct |
| 20 |
Correct |
215 ms |
20196 KB |
Output is correct |
