#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++;}
//for(auto [i, j]:v)cout << i << ' ';
//cout << '\n';
//for(auto [i, j]:v)cout << j << ' ';
//cout << '\n';
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:70:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
70 | while(rans.size() < n)rans.pb({});
| ~~~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
1368 KB |
Output isn't correct |
| 2 |
Incorrect |
15 ms |
1524 KB |
Output isn't correct |
| 3 |
Incorrect |
20 ms |
1528 KB |
Output isn't correct |
| 4 |
Incorrect |
19 ms |
1628 KB |
Output isn't correct |
| 5 |
Incorrect |
15 ms |
1368 KB |
Output isn't correct |
| 6 |
Incorrect |
16 ms |
1372 KB |
Output isn't correct |
| 7 |
Incorrect |
15 ms |
1372 KB |
Output isn't correct |
| 8 |
Incorrect |
14 ms |
1520 KB |
Output isn't correct |
| 9 |
Incorrect |
306 ms |
10220 KB |
Output isn't correct |
| 10 |
Incorrect |
295 ms |
10240 KB |
Output isn't correct |
| 11 |
Correct |
72 ms |
3168 KB |
Output is correct |
| 12 |
Incorrect |
126 ms |
6012 KB |
Output isn't correct |
| 13 |
Correct |
205 ms |
8416 KB |
Output is correct |
| 14 |
Incorrect |
400 ms |
12196 KB |
Output isn't correct |
| 15 |
Incorrect |
351 ms |
12876 KB |
Output isn't correct |
| 16 |
Correct |
568 ms |
16936 KB |
Output is correct |
| 17 |
Correct |
642 ms |
19784 KB |
Output is correct |
| 18 |
Correct |
512 ms |
21872 KB |
Output is correct |
| 19 |
Incorrect |
673 ms |
26244 KB |
Output isn't correct |
| 20 |
Correct |
648 ms |
19924 KB |
Output is correct |
