/*
BY: shalekberli (Shahin Alekberli)
LANG: C++
Maybe IOI?
*/
// #pragma GCC optimize("O3")
// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
//MACROS//
#define need_for_speed ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define _crt_secure_no_warnings
#define endl '\n'
#define pb push_back
#define pf push_front
#define mp make_pair
#define INF 0x3F3F3F3F
#define INFL 0x3F3F3F3F3F3F3F3FLL
#define UB upper_bound
#define LB lower_bound
#define F first
#define S second
#define mod 1000000007LL
#define MOD 998244353LL
#define MoD 16714589LL
#define moD 1000000LL;
#define Max 1e12
#define ll long long
#define lld long double
#define usi unsigned int
#define ull unsigned long long
#define sz(x) (int)x.size()
#define all(v) v.begin(), v.end()
#define pll pair<ll, ll>
#define pii pair<int, int>
#define pcc pair<char, char>
#define fix(n, k) fixed << setprecision((k)) << (n)
#define loop1(i, n, d) for (ll i = 1; i <= (n); i += (d))
#define loop0(i, n, d) for (ll i = 0; i < (n); i += (d))
#define loop(i, k, n, d) for(ll i = (k);i <= (n);i += (d))
#define loopr(i, k, n, d) for (ll i = (k); i >= (n); i -= (d))
#define loopch(i, k, n, d) for(char i = (k); i <= (n);i += (d))
#define loopchr(i, k, n, d) for(char i = (k); i >= (n);i -= (d))
#define read(x) for(auto &i: x) cin >> i
#define readi(x) for(int &i : x) cin >> i
#define readll(x) for(ll &i : x) cin >> i
#define readp(x) for(auto &i : x) cin >> i.F >> i.S;
#define write(x) for(auto &i: x) cout << i << " "
#define writend(x) for(auto &i: x) cout << i << endl
#define writep(x) for(auto &i: x) cout << i.F << " " << i.S << endl
#define alphalower "abcdefghijklmnopqrstuvwxyz"
#define alphaupper "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
using namespace std;
/* ll pw(ll a, ll b){
if(b == 0) return 1;
if(b == 1) return a;
if(b & 1) return a * pw(a, b - 1);
return pw((a * a), b / 2);
} */
/* ll pwmod(ll a, ll b, ll m){
a %= m;
if(b == 0) return 1;
if(b == 1) return a;
if(b & 1) return (a * pwmod(a, b - 1, m)) % m;
return pwmod((a * a) % m, b / 2, m);
} */
int n, d, m;
vector<int> days;
vector<pii> jobs;
vector<vector<int>> ansjobs;
bool validate(int machines){
int idx = 0;
vector<vector<int>> curres(n);
loop1(day, n, 1){
loop0(i, machines, 1){
if(jobs[idx].F > day) break;
if(jobs[idx].F + d >= day){
curres[day - 1].pb(jobs[idx++].S);
}
else{
return false;
}
if(idx == m){
ansjobs = curres;
return true;
}
}
}
return false;
}
void solve(){
cin >> n >> d >> m;
days.resize(m);
loop0(i, m, 1){
cin >> days[i];
jobs.pb({days[i], i + 1});
}
sort(all(jobs));
int l = 1, r = m, ans = m;
//ans = r;
while(l <= r){
int mid = (l + r) / 2;
if(validate(mid)){
ans = min(ans, mid);
r = mid - 1;
}
else{
l = mid + 1;
}
}
cout << ans << endl;
loop0(i, n, 1){
for(auto &to : ansjobs[i]){
cout << to << " ";
}
cout << 0 << endl;
}
}
void Tour_de_Force(string head_hunter){
string head_hunter1 = head_hunter + ".in";
freopen(head_hunter1.c_str() , "r", stdin);
string head_hunter2 = head_hunter + ".out";
freopen(head_hunter2.c_str() , "w", stdout);
}
int main(){
need_for_speed
//Tour_de_Force("sabotage");
solve();
/* ll t; cin >> t;
while(t--){
solve();
} */
cerr << endl << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}
Compilation message
jobs.cpp: In function 'void Tour_de_Force(std::string)':
jobs.cpp:132:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
132 | freopen(head_hunter1.c_str() , "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:134:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
134 | freopen(head_hunter2.c_str() , "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
3748 KB |
Output is correct |
| 2 |
Correct |
26 ms |
3572 KB |
Output is correct |
| 3 |
Correct |
25 ms |
3656 KB |
Output is correct |
| 4 |
Correct |
25 ms |
3664 KB |
Output is correct |
| 5 |
Correct |
27 ms |
3612 KB |
Output is correct |
| 6 |
Correct |
25 ms |
3664 KB |
Output is correct |
| 7 |
Correct |
26 ms |
3724 KB |
Output is correct |
| 8 |
Correct |
26 ms |
3704 KB |
Output is correct |
| 9 |
Correct |
48 ms |
8084 KB |
Output is correct |
| 10 |
Correct |
46 ms |
8228 KB |
Output is correct |
| 11 |
Correct |
34 ms |
3160 KB |
Output is correct |
| 12 |
Correct |
79 ms |
6156 KB |
Output is correct |
| 13 |
Correct |
104 ms |
9572 KB |
Output is correct |
| 14 |
Correct |
160 ms |
13188 KB |
Output is correct |
| 15 |
Correct |
167 ms |
14744 KB |
Output is correct |
| 16 |
Correct |
226 ms |
18148 KB |
Output is correct |
| 17 |
Correct |
285 ms |
22832 KB |
Output is correct |
| 18 |
Correct |
280 ms |
23824 KB |
Output is correct |
| 19 |
Correct |
330 ms |
30640 KB |
Output is correct |
| 20 |
Correct |
283 ms |
22776 KB |
Output is correct |
