#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;
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();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
1372 KB |
Output isn't correct |
| 2 |
Incorrect |
14 ms |
1372 KB |
Output isn't correct |
| 3 |
Incorrect |
14 ms |
1368 KB |
Output isn't correct |
| 4 |
Incorrect |
14 ms |
1368 KB |
Output isn't correct |
| 5 |
Incorrect |
25 ms |
1336 KB |
Output isn't correct |
| 6 |
Incorrect |
18 ms |
1368 KB |
Output isn't correct |
| 7 |
Incorrect |
14 ms |
1372 KB |
Output isn't correct |
| 8 |
Incorrect |
14 ms |
1372 KB |
Output isn't correct |
| 9 |
Incorrect |
63 ms |
3200 KB |
Unexpected end of file - int32 expected |
| 10 |
Incorrect |
62 ms |
3212 KB |
Unexpected end of file - int32 expected |
| 11 |
Incorrect |
76 ms |
3392 KB |
Unexpected end of file - int32 expected |
| 12 |
Incorrect |
129 ms |
6484 KB |
Output isn't correct |
| 13 |
Incorrect |
210 ms |
9548 KB |
Unexpected end of file - int32 expected |
| 14 |
Incorrect |
396 ms |
13544 KB |
Output isn't correct |
| 15 |
Incorrect |
307 ms |
13392 KB |
Output isn't correct |
| 16 |
Incorrect |
567 ms |
19900 KB |
Unexpected end of file - int32 expected |
| 17 |
Incorrect |
663 ms |
22964 KB |
Unexpected end of file - int32 expected |
| 18 |
Incorrect |
484 ms |
22156 KB |
Unexpected end of file - int32 expected |
| 19 |
Incorrect |
528 ms |
27160 KB |
Unexpected end of file - int32 expected |
| 20 |
Incorrect |
616 ms |
22968 KB |
Unexpected end of file - int32 expected |
