#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)
void solve(){
int 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 = [&](int x) -> bool{
vector<vector<int>> rans;
int 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;
};
int l = 1, r = m, ans = m;
while(l <= r){
int 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 'int' [-Wsign-compare]
67 | while(rans.size() < n)rans.pb({});
| ~~~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
1116 KB |
Output isn't correct |
| 2 |
Incorrect |
8 ms |
1116 KB |
Output isn't correct |
| 3 |
Incorrect |
10 ms |
1116 KB |
Output isn't correct |
| 4 |
Incorrect |
8 ms |
1112 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 |
9 ms |
1112 KB |
Output isn't correct |
| 8 |
Incorrect |
8 ms |
1116 KB |
Output isn't correct |
| 9 |
Correct |
52 ms |
9872 KB |
Output is correct |
| 10 |
Correct |
49 ms |
9960 KB |
Output is correct |
| 11 |
Correct |
26 ms |
2640 KB |
Output is correct |
| 12 |
Incorrect |
53 ms |
5200 KB |
Output isn't correct |
| 13 |
Correct |
76 ms |
7504 KB |
Output is correct |
| 14 |
Incorrect |
124 ms |
10656 KB |
Output isn't correct |
| 15 |
Incorrect |
125 ms |
11856 KB |
Output isn't correct |
| 16 |
Correct |
177 ms |
15268 KB |
Output is correct |
| 17 |
Correct |
203 ms |
17792 KB |
Output is correct |
| 18 |
Correct |
212 ms |
20088 KB |
Output is correct |
| 19 |
Correct |
260 ms |
24144 KB |
Output is correct |
| 20 |
Correct |
233 ms |
18036 KB |
Output is correct |
