#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, m);
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 |
621 ms |
11980 KB |
Output isn't correct |
| 2 |
Incorrect |
620 ms |
12088 KB |
Output isn't correct |
| 3 |
Incorrect |
635 ms |
12264 KB |
Output isn't correct |
| 4 |
Incorrect |
616 ms |
11960 KB |
Output isn't correct |
| 5 |
Incorrect |
673 ms |
12172 KB |
Output isn't correct |
| 6 |
Incorrect |
615 ms |
11992 KB |
Output isn't correct |
| 7 |
Incorrect |
613 ms |
12056 KB |
Output isn't correct |
| 8 |
Incorrect |
649 ms |
12064 KB |
Output isn't correct |
| 9 |
Incorrect |
390 ms |
11576 KB |
Output isn't correct |
| 10 |
Incorrect |
454 ms |
11552 KB |
Output isn't correct |
| 11 |
Correct |
255 ms |
11496 KB |
Output is correct |
| 12 |
Incorrect |
609 ms |
17800 KB |
Output isn't correct |
| 13 |
Correct |
930 ms |
26724 KB |
Output is correct |
| 14 |
Execution timed out |
1091 ms |
29864 KB |
Time limit exceeded |
| 15 |
Execution timed out |
1083 ms |
34832 KB |
Time limit exceeded |
| 16 |
Execution timed out |
1091 ms |
41488 KB |
Time limit exceeded |
| 17 |
Execution timed out |
1096 ms |
50228 KB |
Time limit exceeded |
| 18 |
Execution timed out |
1088 ms |
52392 KB |
Time limit exceeded |
| 19 |
Execution timed out |
1097 ms |
56256 KB |
Time limit exceeded |
| 20 |
Execution timed out |
1088 ms |
50148 KB |
Time limit exceeded |
