Submission #563767

#	Time	Username	Problem	Language	Result	Execution time	Memory
563767		Mistri_	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	3 ms	340 KiB

jobs

#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((int)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( x<m && temp[x].first <= i){
                ans[i].push_back(temp[x].second);
                x++;
            }
        }
        sort(ans[i].begin(),ans[i].end());
        if(x==m)break;
    }

    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 = 1e5 + 1;
    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 =1;j<(int)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 (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:163:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  163 |  freopen(inputStr.c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:164:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  164 |  freopen(outputStr.c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100