#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define vb vector<bool>
#define vi vector<int>
#define vvi vector<vi>
#define fi first
#define se second
#define pii pair<int, int>
#define sz(x) (int)(x).size()
signed main(){
//ios_base::sync_with_stdio(false); cin.tie(0);
int n, d, m;
cin >> n >> d >> m;
vector<pii> job(m);
vvi d2i(n + 1);
for(int i = 0; i < m; i++){
cin >> job[i].fi;
job[i].se;
d2i[job[i].fi].emplace_back(i);
}
//sort(job.begin(), job.end());
auto check = [&](int val) -> bool {
deque<pii> dq;
for(int day = 1; day <= n; day++){
int temp = val;
while(!dq.empty() && temp){
pii cur = dq.front();
dq.pop_front();
if(cur.fi + d < day) return false;
int minus = min(cur.se, temp);
cur.se -= minus, temp -= minus;
if(cur.se){
dq.emplace_front(cur);
}
}
int rem = max(sz(d2i[day]) - temp, 0ll);
if(rem){
dq.emplace_back(day, rem);
}
}
return (dq.empty());
};
auto bs = [&]() -> int {
int lo = 1, hi = m, ret = 1, mid;
while(hi >= lo){
mid = lo + (hi - lo) / 2;
if(check(mid)){
hi = mid - 1;
ret = mid;
}
else{
lo = mid + 1;
}
}
return ret;
};
int val = bs();
vvi ans(n + 1);
queue<int> q;
for(int day = 1; day <= n; day++){
for(int i = 0; i < val; i++){
if(!q.empty()){
ans[day].emplace_back(q.front() + 1);
q.pop();
}
else if(sz(d2i[day])){
ans[day].emplace_back(d2i[day].back() + 1);
d2i[day].pop_back();
}
else break;
}
}
for(int day = 1; day <= n; day++){
for(int &i : ans[day]){
cout << i << " ";
}
cout << "0\n";
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
19 ms |
4292 KB |
Output isn't correct |
2 |
Incorrect |
16 ms |
4292 KB |
Output isn't correct |
3 |
Incorrect |
17 ms |
4292 KB |
Output isn't correct |
4 |
Incorrect |
17 ms |
4300 KB |
Output isn't correct |
5 |
Incorrect |
16 ms |
4292 KB |
Output isn't correct |
6 |
Incorrect |
16 ms |
4292 KB |
Output isn't correct |
7 |
Incorrect |
17 ms |
4292 KB |
Output isn't correct |
8 |
Incorrect |
17 ms |
4292 KB |
Output isn't correct |
9 |
Incorrect |
23 ms |
9356 KB |
Expected EOLN |
10 |
Incorrect |
41 ms |
9288 KB |
Expected EOLN |
11 |
Incorrect |
39 ms |
4680 KB |
Expected EOLN |
12 |
Incorrect |
40 ms |
8520 KB |
Expected EOLN |
13 |
Incorrect |
62 ms |
15432 KB |
Expected EOLN |
14 |
Incorrect |
120 ms |
18892 KB |
Expected EOLN |
15 |
Incorrect |
109 ms |
21064 KB |
Expected EOLN |
16 |
Incorrect |
156 ms |
26452 KB |
Expected EOLN |
17 |
Runtime error |
186 ms |
34632 KB |
Memory limit exceeded |
18 |
Runtime error |
174 ms |
35584 KB |
Memory limit exceeded |
19 |
Runtime error |
194 ms |
42312 KB |
Memory limit exceeded |
20 |
Runtime error |
177 ms |
34628 KB |
Memory limit exceeded |