// REMEMBERING THE PAST , CAN AVOID REPEAT THE SAME
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define inf 9000000000000000000
typedef long long ll;
#define f first
#define s second
#define all(x) begin(x), end(x)
//pbds
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<pair<int,int>, null_type, less_equal<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update> pbds; // find_by_order, order_of_key
void setIO(string s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
ll GCD(ll a,ll b){
if(b>a){
swap(a,b);
}
if(b==0){
return a;
}
return GCD(b,a%b);
}
ll power(ll x,ll y){
ll res=1;
while (y){
if (y & 1){
res=(res*x)%mod;
}
x=(x*x)%mod;
y=y>>1;
}
return res%mod;
}
ll add(ll x,ll y){
return (x+y)%mod;
}
ll sub(ll x,ll y){
return (x-y+mod)%mod;
}
ll mul(ll x,ll y){
return (x*y)%mod;
}
ll divide(ll x,ll y){
return (x*(power(y,mod-2)))%mod;
}
//int const N=2e6+10;
//ll fact[N];
//ll NCR(int n,int r){
// ll num=fact[n];
// ll deno=mul(fact[r],fact[n-r]);
// ll ans=divide(num,deno);
// return ans;
//}
//bool isPrime[N];
//int primeFactor[N];
//vector<int> primes;
//void checkPrime(){
// memset(isPrime,true,sizeof(isPrime));
// memset(primeFactor,0,sizeof(primeFactor));
// int i=2;
// isPrime[0]=isPrime[1]=false;
// while(i*i<N){
// if(isPrime[i]){
// for(int j=i*i;j<N;j+=i){
// isPrime[j]=false;
// primeFactor[j]=i;
// }
// }
// i++;
// }
//
// for(int i=2;i<N;i++){
// if(isPrime[i]){
// primes.push_back(i);
// }
// if(primeFactor[i]==0){
// primeFactor[i]=i;
// }
// }
//}
bool checkPalindrome(int l,int r,string &s){
while(l<r){
if(s[l]!=s[r]){
return false;
}
l++;
r--;
}
return true;
}
//--> base cases 1,2.. ?
//--> BS on answer ?
//--> DP max or min val?
//--> GCD , n^0.5 ?
//--> brute force ?
//--> use long double ?
void solve() {
int n, d, m, x;
cin >> n >> d >> m;
vector<pair<int, int>> jobs(m);
for (int i = 0; i < m; i++) {
cin >> x;
jobs[i] = {x, i + 1};
}
sort(all(jobs));
ll l = 1, r = m, mid, ans;
while (l <= r) {
mid = l + (r - l) / 2;
int i = 1, j = 0, cnt = 0;
bool flag = true;
while (j < m) {
while (j < m && cnt < mid && jobs[j].f <= i) {
if (i - jobs[j].f > d) {
flag = false;
break;
}
cnt++;
j++;
}
if (!flag) break;
i++;
cnt = 0;
}
if (flag) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
cout << ans << "\n";
int j = 0, i = 1, cnt = 0;
while (j < m || i <= n) {
while (j < m && cnt < ans && jobs[j].f <= i) {
cnt++;
cout << jobs[j].s << " ";
j++;
}
cout << "0\n";
i++;
cnt = 0;
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//setIO("problemname");
int t=1;
// cin>>t;
//checkPrime();
//fact[0]=1;
//for(int i=1;i<N;i++){
//fact[i]=mul(i,fact[i-1]);
//}
for(int T=1;T<=t;T++){
solve();
}
return 0;
}
Compilation message
jobs.cpp: In function 'void setIO(std::string)':
jobs.cpp:19:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
19 | freopen((s + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:20:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
20 | freopen((s + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp: In function 'void solve()':
jobs.cpp:122:24: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
122 | ll l = 1, r = m, mid, ans;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
1988 KB |
Output is correct |
| 2 |
Correct |
19 ms |
1996 KB |
Output is correct |
| 3 |
Correct |
17 ms |
1972 KB |
Output is correct |
| 4 |
Correct |
35 ms |
1996 KB |
Output is correct |
| 5 |
Correct |
17 ms |
1972 KB |
Output is correct |
| 6 |
Correct |
18 ms |
1996 KB |
Output is correct |
| 7 |
Correct |
23 ms |
1972 KB |
Output is correct |
| 8 |
Correct |
18 ms |
2008 KB |
Output is correct |
| 9 |
Correct |
27 ms |
2124 KB |
Output is correct |
| 10 |
Correct |
28 ms |
2124 KB |
Output is correct |
| 11 |
Correct |
24 ms |
1992 KB |
Output is correct |
| 12 |
Correct |
50 ms |
3912 KB |
Output is correct |
| 13 |
Correct |
73 ms |
5800 KB |
Output is correct |
| 14 |
Correct |
123 ms |
8040 KB |
Output is correct |
| 15 |
Correct |
127 ms |
9460 KB |
Output is correct |
| 16 |
Correct |
161 ms |
11904 KB |
Output is correct |
| 17 |
Correct |
185 ms |
13876 KB |
Output is correct |
| 18 |
Correct |
220 ms |
15036 KB |
Output is correct |
| 19 |
Correct |
251 ms |
17124 KB |
Output is correct |
| 20 |
Correct |
194 ms |
13972 KB |
Output is correct |
