#include <bits/stdc++.h>
#include<time.h>
#include<chrono>
#include<unordered_set>
#include<unordered_map>
#define nline std::cout<<'\n';
#define yes std::cout<<"YES";
#define no std::cout<<"NO";
#define md 1e9 +7;
using namespace std;
struct custom_hash {static uint64_t splitmix64(uint64_t x) {x += 0x9e3779b97f4a7c15;x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;x = (x ^ (x >> 27)) * 0x94d049bb133111eb;return x ^ (x >> 31);}size_t operator()(uint64_t x) const {static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();return splitmix64(x + FIXED_RANDOM);}};
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template< typename T>void input(T* arr, int n){for( int i =0;i<n;i++){std::cin>>arr[i];}}
template<class T> void input_vector( std::vector<T>&v, int n){for( int i=0;i<n;i++){std::cin>>v[i];}}
template<class T> int get_digits( T x){ int count{};while( x > 0){x = x/10;count++;}return count;}
ll gcd(ll a, ll b){if(a==0) return b;else if(b==0 )return a;else return gcd(b,a%b);}
int n,D,m;
std::vector<int>v;
std::vector<int> day;
bool good(int mid)
{
std::deque<int>d;
for(int i=1;i<=n;i++)
{
int nw = mid;
if(d.empty())
{
if(day[i] <= nw){
continue;
}else{
d.push_back(day[i] - nw);
}
}
else{
while(nw>0 && !d.empty())
{
nw = max(0,nw - d.front());
d.front() = max(0,d.front() - nw);
if(d.front() == 0) d.pop_front();
}
if(nw == 0)
{
if(day[i] != 0) d.push_back(day[i]);
}
else{
if(day[i] <= nw){
continue;
}else{
d.push_back(day[i] - nw);
}
}
}
if(d.size() > D) return false;
}
return true;
}
vector<vector<int>> help(int r)
{
std::vector<vector<int>> ans(n+1,vector<int>());
std::vector<pair<int,int>> temp(m,{0,0});
for(int i =0;i<m;i++)
{
temp[i] = {v[i],i+1};
}
sort(temp.begin(),temp.end());
int x = 0;
for(int i =1;i<=n;i++)
{
for(int j = 0;j<r;j++)
{
if( j<m && temp[x].first <= i){
ans[i].push_back(temp[x].second);
x++;
}
}
}
return ans;
}
void solve(){
std::cin>>n>>D>>m;
v.assign(m,0);
input_vector(v,m);
day.assign(n+1,0);
int maxi = 0;
for(int i =0;i<m;i++)
{
day[v[i]]++;
maxi = max(maxi,day[v[i]]);
}
int l = 0;
int r = maxi;
int mid = l + (r-l)/2;
while(l+1<r)
{
if(good(mid))
{
r = mid;
}else l = mid;
mid = l + (r-l)/2;
}
auto ans = help(r);
std::cout<<r;
nline;
for(int i =1;i<=n;i++)
{
for(int j =0;j<ans[i].size();j++)
{
std::cout<<ans[i][j]<<" ";
}
std::cout<<0;
nline
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
std::string IOstr = "";
std::string inputStr;
std::string outputStr;
if(IOstr == ""){
inputStr = "in.in";
outputStr = "out.out";
}
else{
inputStr = IOstr + ".in";
outputStr = IOstr + ".out";
}
// freopen(inputStr.c_str(), "r", stdin);
// freopen(outputStr.c_str(), "w", stdout);
solve();
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// ///
/// ///
/// Mistri_ fumll coding bamji ///
/// ///
/// ///
/// ///
////////////////////////////////////////////////////////////////////////////////////////////////////////////
//
//
//
// mistri coder
//
//
//
// ⬤⬤ ⬤⬤ ⬤⬤
// ⬤⬤⬤ ⬤⬤⬤ ⬤ ⬤⬤⬤⬤⬤ ⬤⬤ ⬤⬤ ⬤⬤⬤ ⬤
// ⬤⬤ ⬤⬤ ⬤⬤ ⬤⬤ ⬤⬤⬤⬤⬤⬤ ⬤⬤⬤ ⬤
// ⬤⬤ ⬤⬤ ⬤⬤ ⬤⬤⬤ ⬤⬤ ⬤⬤ ⬤⬤
// ⬤⬤ ⬤⬤ ⬤⬤ ⬤⬤ ⬤⬤ ⬤⬤ ⬤⬤
// ⬤⬤ ⬤⬤ ⬤⬤ ⬤⬤⬤⬤⬤ ⬤⬤ ⬤⬤ ⬤⬤
Compilation message
jobs.cpp: In function 'bool good(int)':
jobs.cpp:64:21: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
64 | if(d.size() > D) return false;
| ~~~~~~~~~^~~
jobs.cpp: In function 'void solve()':
jobs.cpp:133:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
133 | for(int j =0;j<ans[i].size();j++)
| ~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
2004 KB |
Output isn't correct |
| 2 |
Incorrect |
11 ms |
2004 KB |
Output isn't correct |
| 3 |
Incorrect |
13 ms |
2132 KB |
Output isn't correct |
| 4 |
Incorrect |
11 ms |
2008 KB |
Output isn't correct |
| 5 |
Incorrect |
11 ms |
2004 KB |
Output isn't correct |
| 6 |
Incorrect |
11 ms |
2004 KB |
Output isn't correct |
| 7 |
Incorrect |
11 ms |
1996 KB |
Output isn't correct |
| 8 |
Incorrect |
12 ms |
2004 KB |
Output isn't correct |
| 9 |
Incorrect |
365 ms |
4744 KB |
Output isn't correct |
| 10 |
Incorrect |
356 ms |
4692 KB |
Output isn't correct |
| 11 |
Incorrect |
24 ms |
2000 KB |
Output isn't correct |
| 12 |
Incorrect |
50 ms |
3600 KB |
Output isn't correct |
| 13 |
Incorrect |
75 ms |
5792 KB |
Output isn't correct |
| 14 |
Incorrect |
102 ms |
7600 KB |
Output isn't correct |
| 15 |
Incorrect |
125 ms |
8148 KB |
Output isn't correct |
| 16 |
Incorrect |
156 ms |
11116 KB |
Output isn't correct |
| 17 |
Incorrect |
184 ms |
13416 KB |
Output isn't correct |
| 18 |
Incorrect |
203 ms |
13952 KB |
Output isn't correct |
| 19 |
Incorrect |
295 ms |
17796 KB |
Output isn't correct |
| 20 |
Incorrect |
191 ms |
13424 KB |
Output isn't correct |
