#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)
bool works=true;
ll day=1;
ll left=x;
for (int i=0; i<nums.size(); i++){
if (day-nums[i].val>d){
works=false;
break;
}
day=min(day, nums[i].val);
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;
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:37:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for (int i=0; i<nums.size(); i++){
| ~^~~~~~~~~~~~
jobs.cpp:56:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for (int j=0; j<req[i].size(); j++){
| ~^~~~~~~~~~~~~~
jobs.cpp: In function 'int main()':
jobs.cpp:107:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | for (int j=0; j<last[i].size(); j++){
| ~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
93 ms |
15740 KB |
Output isn't correct |
| 2 |
Incorrect |
92 ms |
15744 KB |
Output isn't correct |
| 3 |
Incorrect |
103 ms |
15292 KB |
Output isn't correct |
| 4 |
Incorrect |
94 ms |
15672 KB |
Output isn't correct |
| 5 |
Incorrect |
96 ms |
16604 KB |
Output isn't correct |
| 6 |
Incorrect |
93 ms |
16116 KB |
Output isn't correct |
| 7 |
Incorrect |
94 ms |
16676 KB |
Output isn't correct |
| 8 |
Incorrect |
94 ms |
16528 KB |
Output isn't correct |
| 9 |
Incorrect |
238 ms |
13048 KB |
Output isn't correct |
| 10 |
Incorrect |
230 ms |
13108 KB |
Output isn't correct |
| 11 |
Incorrect |
89 ms |
17208 KB |
Output isn't correct |
| 12 |
Incorrect |
163 ms |
28984 KB |
Output isn't correct |
| 13 |
Runtime error |
241 ms |
41788 KB |
Memory limit exceeded |
| 14 |
Runtime error |
361 ms |
64904 KB |
Memory limit exceeded |
| 15 |
Runtime error |
363 ms |
65536 KB |
Memory limit exceeded |
| 16 |
Runtime error |
323 ms |
65540 KB |
Execution killed with signal 9 |
| 17 |
Runtime error |
361 ms |
65540 KB |
Execution killed with signal 9 |
| 18 |
Runtime error |
393 ms |
65540 KB |
Execution killed with signal 9 |
| 19 |
Runtime error |
377 ms |
65540 KB |
Execution killed with signal 9 |
| 20 |
Runtime error |
341 ms |
65536 KB |
Execution killed with signal 9 |
