#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MN=1e6+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;
ll day=1;
ll left=x;
for (int i=0; i<nums.size(); i++){
if (day-nums[i].val>d){
works=false;
break;
}
day=max(day, nums[i].val);
store[day-1].pb(nums[i].index);
left--;
if (left==0){
left=x;
day++;
}
}
// 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:49:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for (int i=0; i<nums.size(); i++){
| ~^~~~~~~~~~~~
jobs.cpp:91:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for (int j=0; j<store[i].size(); j++){
| ~^~~~~~~~~~~~~~~~
jobs.cpp: In function 'int main()':
jobs.cpp:138:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
138 | for (int j=0; j<adj[i].size(); j++){
| ~^~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
82 ms |
51552 KB |
Memory limit exceeded |
| 2 |
Runtime error |
79 ms |
51604 KB |
Memory limit exceeded |
| 3 |
Runtime error |
79 ms |
51480 KB |
Memory limit exceeded |
| 4 |
Runtime error |
81 ms |
51572 KB |
Memory limit exceeded |
| 5 |
Runtime error |
78 ms |
51460 KB |
Memory limit exceeded |
| 6 |
Runtime error |
81 ms |
51640 KB |
Memory limit exceeded |
| 7 |
Runtime error |
80 ms |
51544 KB |
Memory limit exceeded |
| 8 |
Runtime error |
81 ms |
51452 KB |
Memory limit exceeded |
| 9 |
Runtime error |
233 ms |
52400 KB |
Memory limit exceeded |
| 10 |
Runtime error |
229 ms |
52112 KB |
Memory limit exceeded |
| 11 |
Runtime error |
81 ms |
53424 KB |
Memory limit exceeded |
| 12 |
Runtime error |
136 ms |
58940 KB |
Memory limit exceeded |
| 13 |
Runtime error |
196 ms |
65544 KB |
Execution killed with signal 9 |
| 14 |
Runtime error |
179 ms |
65540 KB |
Execution killed with signal 9 |
| 15 |
Runtime error |
157 ms |
65540 KB |
Execution killed with signal 9 |
| 16 |
Runtime error |
188 ms |
65540 KB |
Execution killed with signal 9 |
| 17 |
Runtime error |
188 ms |
65540 KB |
Execution killed with signal 9 |
| 18 |
Runtime error |
186 ms |
65540 KB |
Execution killed with signal 9 |
| 19 |
Runtime error |
205 ms |
65540 KB |
Execution killed with signal 9 |
| 20 |
Runtime error |
187 ms |
65540 KB |
Execution killed with signal 9 |
