#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MN=1e5+10;
const int MOD=1e9+7;
using pi = pair<ll, ll>;
#define pb push_back
#define mp make_pair
#define MAX LLONG_MAX
#define MIN LLONG_MIN
#define MAX_SIZE 1000005
#define lcm(a, b) (a*b)/__gcd(a, b)
struct Edge{
ll val, index;
};
bool comp(const Edge& x, const Edge& y){
return x.val < y.val;
}
ll n, d, m;
vector<Edge> nums;
vector<ll> adj[MN];
vector<ll> store[MN];
bool f(ll x){
// binary search check (greedy)
if (x>=m){
return true;
}
for (int i=0; i<n; i++){
store[i].clear();
}
multiset<ll> curr;
for (int i=0; i<x; i++){
curr.insert(0);
}
bool works=true;
for (int i=0; i<nums.size(); i++){
auto first=curr.begin();
if (nums[i].val>*first){
store[nums[i].val-1].pb(nums[i].index);
curr.erase(first);
curr.insert(nums[i].val);
}
else{
ll diff=*first-nums[i].val+1;
if (diff>=d){
works=false;
break;
}
else{
store[*first].pb(nums[i].index);
curr.erase(first);
curr.insert(*first + 1);
}
}
}
if (works){
for (int i=0; i<n; i++){
adj[i].clear();
}
for (int i=0; i<n; i++){
for (int j=0; j<store[i].size(); j++){
adj[i].pb(store[i][j]);
}
}
return true;
}
else{
return false;
}
}
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);
cin>>n>>d>>m;
for (int i=0; i<m; i++){
ll num; cin>>num;
nums.pb({num, i+1});
}
sort(nums.begin(), nums.end(), comp);
ll ans=binaryMin(1, INT_MAX);
cout<<ans<<endl;
for (int i=0; i<n; i++){
for (int j=0; j<adj[i].size(); j++){
cout<<adj[i][j]<<" ";
}
cout<<0<<endl;
}
}
Compilation message
jobs.cpp: In function 'bool f(ll)':
jobs.cpp:46:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for (int i=0; i<nums.size(); i++){
| ~^~~~~~~~~~~~
jobs.cpp:72:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for (int j=0; j<store[i].size(); j++){
| ~^~~~~~~~~~~~~~~~
jobs.cpp: In function 'int main()':
jobs.cpp:119:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | for (int j=0; j<adj[i].size(); j++){
| ~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
415 ms |
12956 KB |
Output isn't correct |
| 2 |
Incorrect |
422 ms |
12732 KB |
Output isn't correct |
| 3 |
Incorrect |
414 ms |
12728 KB |
Output isn't correct |
| 4 |
Incorrect |
424 ms |
12728 KB |
Output isn't correct |
| 5 |
Incorrect |
412 ms |
12792 KB |
Output isn't correct |
| 6 |
Incorrect |
413 ms |
12856 KB |
Output isn't correct |
| 7 |
Incorrect |
417 ms |
12724 KB |
Output isn't correct |
| 8 |
Incorrect |
420 ms |
12788 KB |
Output isn't correct |
| 9 |
Incorrect |
368 ms |
12520 KB |
Output isn't correct |
| 10 |
Incorrect |
466 ms |
12632 KB |
Output isn't correct |
| 11 |
Correct |
251 ms |
12568 KB |
Output is correct |
| 12 |
Incorrect |
581 ms |
19888 KB |
Output isn't correct |
| 13 |
Correct |
975 ms |
32528 KB |
Output is correct |
| 14 |
Execution timed out |
1086 ms |
33512 KB |
Time limit exceeded |
| 15 |
Execution timed out |
1094 ms |
36124 KB |
Time limit exceeded |
| 16 |
Execution timed out |
1094 ms |
52788 KB |
Time limit exceeded |
| 17 |
Execution timed out |
1090 ms |
59024 KB |
Time limit exceeded |
| 18 |
Execution timed out |
1083 ms |
58824 KB |
Time limit exceeded |
| 19 |
Execution timed out |
1093 ms |
60392 KB |
Time limit exceeded |
| 20 |
Execution timed out |
1099 ms |
59024 KB |
Time limit exceeded |
