#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MN=1e5+10;
const int MOD=1e9+7;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define MAX LLONG_MAX
#define MIN LLONG_MIN
struct Edge{
ll val, index;
};
bool comp(const Edge& x, const Edge& y){
return x.val < y.val;
}
ll d, n;
vector<Edge> nums;
vector<ll> req[MN];
vector<ll> last[MN];
bool f(ll x){
// binary search check (greedy)
if (x>n){
return true;
}
bool works=true;
ll day=1;
ll left=x;
for (int i=0; i<nums.size(); i++){
if (day>nums[i].val){
day=nums[i].val;
left=x;
}
if (day-nums[i].val>d){
works=false;
break;
}
req[day].pb(nums[i].index+1);
left--;
if (left==0){
left=x;
day++;
}
}
if (works){
for (int i=0; i<MN; i++){
last[i].clear();
for (int j=0; j<req[i].size(); j++){
last[i].pb(req[i][j]);
}
}
}
for (int i=0; i<MN; i++){
req[i].clear();
}
return works;
}
ll binaryMin(ll low, ll high){
// for min
ll res=0;
while (low<=high){
ll mid=(low+high)/2;
// cout<<mid<<endl;
if (f(mid)){
res=mid;
high=mid-1;
}
else{
low=mid+1;
}
}
return res;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
ll m; cin>>n>>d>>m;
for (int i=0; i<m; i++){
ll num; cin>>num;
nums.pb({num, i});
}
sort(nums.begin(), nums.end(), comp);
ll ans=binaryMin(1, INT_MAX);
cout<<ans<<endl;
for (int i=1; i<=n; i++){
for (int j=0; j<last[i].size(); j++){
cout<<last[i][j]<<" ";
}
cout<<0<<endl;
}
}
Compilation message
jobs.cpp: In function 'bool first(ll)':
jobs.cpp:41:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for (int i=0; i<nums.size(); i++){
| ~^~~~~~~~~~~~
jobs.cpp:61:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for (int j=0; j<req[i].size(); j++){
| ~^~~~~~~~~~~~~~
jobs.cpp: In function 'int main()':
jobs.cpp:112:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | for (int j=0; j<last[i].size(); j++){
| ~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
63 ms |
11960 KB |
Output isn't correct |
| 2 |
Incorrect |
63 ms |
12048 KB |
Output isn't correct |
| 3 |
Incorrect |
71 ms |
12100 KB |
Output isn't correct |
| 4 |
Incorrect |
63 ms |
12596 KB |
Output isn't correct |
| 5 |
Incorrect |
63 ms |
13480 KB |
Output isn't correct |
| 6 |
Incorrect |
62 ms |
12864 KB |
Output isn't correct |
| 7 |
Incorrect |
64 ms |
13456 KB |
Output isn't correct |
| 8 |
Incorrect |
67 ms |
13452 KB |
Output isn't correct |
| 9 |
Incorrect |
236 ms |
12048 KB |
Output isn't correct |
| 10 |
Incorrect |
227 ms |
12052 KB |
Output isn't correct |
| 11 |
Incorrect |
56 ms |
10804 KB |
Output isn't correct |
| 12 |
Incorrect |
94 ms |
14684 KB |
Output isn't correct |
| 13 |
Incorrect |
158 ms |
19856 KB |
Output isn't correct |
| 14 |
Runtime error |
254 ms |
45476 KB |
Memory limit exceeded |
| 15 |
Incorrect |
212 ms |
27728 KB |
Output isn't correct |
| 16 |
Runtime error |
341 ms |
63940 KB |
Memory limit exceeded |
| 17 |
Runtime error |
257 ms |
65540 KB |
Execution killed with signal 9 |
| 18 |
Runtime error |
381 ms |
58616 KB |
Memory limit exceeded |
| 19 |
Runtime error |
261 ms |
65540 KB |
Execution killed with signal 9 |
| 20 |
Runtime error |
256 ms |
65540 KB |
Execution killed with signal 9 |
