#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define For(i, a, b) for(int i = (a); i < (b); ++i)
#define pb push_back
#define ins insert
#define rsz resize
#define f first
#define s second
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define endl '\n'
using namespace std;
using namespace __gnu_pbds;
void setIO(string name = "")
{
cin.tie(0)->sync_with_stdio(0);
if (sz(name))
{
freopen((name + ".in").c_str(), "r", stdin);
freopen((name + ".out").c_str(), "w", stdout);
}
}
void prt(bool f)
{
// Unfortunatley, atcoder checker rejects YES/NO
cout<<((f)? "Yes\n" : "No\n");
}
using indexed_set = tree<int,null_type,less<int>,
rb_tree_tag,tree_order_statistics_node_update>;
using ll = long long;
using ld = long double;
using str = string;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vb = vector<bool>;
using vs = vector<str>;
using mi = map<int, int>;
using ml = map<ll, ll>;
using si = set<int>;
using sl = set<ll>;
using sc = set<char>;
const ld PI = 2*acos(0.0);
const ld EPS = 1e-11;
const int MOD = 1e9 + 7;
// const int MOD = 998244353;
const int inv2 = (MOD+1)/2;
const ll INF = 1e12;
const int M = 1e6;
const int N = 1e5;
#define int ll
int n, d, m;
int a[M], mp[N+1];
vector<int> v[N+1];
vector<int> p[N+1];
bool ok(int x, bool flag)
{
bool ret = true;
multiset<int> s;
for(int i = 1; i <= n; ++i)
{
v[i].clear();
for(int j = 0; j < mp[i]; ++j)
{
s.ins(i);
}
for(int j = 0; j < x; ++j)
{
if(s.empty()) break;
ret &= i - *s.begin() <= d;
if(flag)
{
v[i].pb(p[*s.begin()].back());
p[*s.begin()].pop_back();
}
s.erase(s.begin());
}
}
return ret;
}
void solve()
{
cin>>n>>d>>m;
for(int i = 0; i < m; ++i)
{
cin>>a[i];
mp[a[i]]++;
p[a[i]].pb(i+1);
}
int L = 1, R = 1e7, mid;
while(L < R)
{
mid = L + (R - L) / 2;
if(ok(mid, false))
{
R = mid;
}
else
{
L = mid+1;
}
}
cout<<L<<endl;
assert(ok(L, true));
for(int i = 1; i <= n; ++i)
{
for(int j = 0; j < sz(v[i]); ++j)
{
cout<<v[i][j];
if(j + 1 != sz(v[i])) cout<<" ";
else cout<<" 0";
}
if(v[i].empty())
{
cout<<"0";
}
if(i != n) cout<<endl;
}
}
int32_t main()
{
setIO();
int t = 1;
// cin>>t;
for(int i = 1; i <= t; ++i)
{
solve();
}
return 0;
}
/*
*/
Compilation message
jobs.cpp: In function 'void setIO(std::string)':
jobs.cpp:19:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
19 | freopen((name + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
20 | freopen((name + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
374 ms |
13080 KB |
Output is correct |
| 2 |
Correct |
340 ms |
13076 KB |
Output is correct |
| 3 |
Correct |
353 ms |
13072 KB |
Output is correct |
| 4 |
Correct |
341 ms |
13076 KB |
Output is correct |
| 5 |
Correct |
378 ms |
13076 KB |
Output is correct |
| 6 |
Correct |
356 ms |
13092 KB |
Output is correct |
| 7 |
Correct |
354 ms |
13072 KB |
Output is correct |
| 8 |
Correct |
366 ms |
13076 KB |
Output is correct |
| 9 |
Correct |
222 ms |
10580 KB |
Output is correct |
| 10 |
Correct |
228 ms |
10980 KB |
Output is correct |
| 11 |
Correct |
146 ms |
9848 KB |
Output is correct |
| 12 |
Correct |
331 ms |
15516 KB |
Output is correct |
| 13 |
Correct |
505 ms |
22820 KB |
Output is correct |
| 14 |
Correct |
600 ms |
26572 KB |
Output is correct |
| 15 |
Correct |
826 ms |
30436 KB |
Output is correct |
| 16 |
Runtime error |
805 ms |
34500 KB |
Memory limit exceeded |
| 17 |
Execution timed out |
1024 ms |
44648 KB |
Time limit exceeded |
| 18 |
Execution timed out |
1044 ms |
32784 KB |
Time limit exceeded |
| 19 |
Execution timed out |
1067 ms |
37840 KB |
Time limit exceeded |
| 20 |
Execution timed out |
1012 ms |
44608 KB |
Time limit exceeded |
