#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;z
#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
//#define int long long
//#define ordst tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag , tree_order_statistics_node_update >
//#define double long double
//template <class F, class _S>
//bool chmin(F &u, const _S &v){
//bool flag = false;
//if ( u > v ){
//u = v; flag |= true;
//}
//return flag;
//}
//template <class F, class _S>
//bool chmax(F &u, const _S &v){
//bool flag = false;
//if ( u < v ){
//u = v; flag |= true;
//}
//return flag;
//}
//const int N = (1<<18) +1, inf = 1e18+200;
//int mod = 998244353;
//int mod = 1000000007;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#define rnd(l, r) uniform_int_distribution <int> (l, r)(rng)
typedef long long ll;
void solve(){
ll n, d, m;
cin >> n >> d >> m;
vector<array<int,2>> v(m);
int ii = 1;
for(auto &[f, s]:v){cin >> f; s = ii++;}
sort(all(v));
vector<vector<int>> ans2;
auto ok = [&](ll x) -> bool{
vector<vector<int>> rans;
ll cnt = x, day = 1, it = 0;
while(day < n){
bool ok = 1;
vector<int> ad;
cnt = x;
while(cnt-- && it < m && v[it][0] <= day){
if(v[it][0]+d < day)return false;
ad.pb(v[it][1]);
it++;
ok = 0;
//cout << it << '\n';
}
//cout << x << '\n';
day++;
rans.pb(ad);
if(ok)break;
}
if(it < m)return false;
while(rans.size() < n)rans.pb({});
ans2 = rans;
return true;
};
ll l = 1, r = 1e15, ans = m;
while(l <= r){
ll md = (l+r)>>1;
//cout << md << '\n';
if(ok(md)){
ans = md;
r = md-1;
}else l = md+1;
}
//for(int i = r+100; i >= r-100; i--){
//if(ok(i)){
//ans = i;
//}else break;
//}
ok(ans);
cout << ans << '\n';
for(auto i:ans2){
for(auto j:i)cout << j << ' ';
cout << "0\n";
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt = 1;
//cin >> tt;
while(tt--){
solve();
}
}
Compilation message
jobs.cpp: In lambda function:
jobs.cpp:67:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
67 | while(rans.size() < n)rans.pb({});
| ~~~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
1112 KB |
Output isn't correct |
| 2 |
Incorrect |
8 ms |
1112 KB |
Output isn't correct |
| 3 |
Incorrect |
8 ms |
1112 KB |
Output isn't correct |
| 4 |
Incorrect |
10 ms |
1116 KB |
Output isn't correct |
| 5 |
Incorrect |
8 ms |
1116 KB |
Output isn't correct |
| 6 |
Incorrect |
8 ms |
1116 KB |
Output isn't correct |
| 7 |
Incorrect |
8 ms |
1116 KB |
Output isn't correct |
| 8 |
Incorrect |
8 ms |
1116 KB |
Output isn't correct |
| 9 |
Correct |
127 ms |
9984 KB |
Output is correct |
| 10 |
Correct |
123 ms |
9988 KB |
Output is correct |
| 11 |
Correct |
45 ms |
2608 KB |
Output is correct |
| 12 |
Incorrect |
70 ms |
5196 KB |
Output isn't correct |
| 13 |
Correct |
103 ms |
7508 KB |
Output is correct |
| 14 |
Incorrect |
198 ms |
10656 KB |
Output isn't correct |
| 15 |
Incorrect |
164 ms |
11788 KB |
Output isn't correct |
| 16 |
Correct |
264 ms |
15268 KB |
Output is correct |
| 17 |
Correct |
314 ms |
17776 KB |
Output is correct |
| 18 |
Correct |
270 ms |
20008 KB |
Output is correct |
| 19 |
Correct |
399 ms |
24336 KB |
Output is correct |
| 20 |
Correct |
310 ms |
17824 KB |
Output is correct |
