Submission #684979

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
684979	2023-01-23T03:44:28 Z	nikhil_kumart21	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	164 ms	29624 KB

jobs

#include <bits/stdc++.h>

using namespace std;

typedef int ll;
#define endl "\n";

void setIO(string s) {
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}
vector<vector<ll>>v;
vector<ll>row;
vector<vector<ll>>A,M;
ll fun(ll a[],ll n,ll mid,ll d,ll done){
    deque<ll>dq;
    v.clear();
    for(ll i=1;i<=n;++i){
        if(dq.size()>d)return 0;
        ll x=mid;
        row.clear();
        dq.push_back(a[i]);
        while(!dq.empty()){
            if(dq.front()<=x){
                x-=dq.front();
                if(dq.front()!=0&&done){
                    for(ll j=0;j<dq.front();++j){
                        row.push_back(i-dq.size()+1);
                    }
                }
                dq.pop_front();
            }
            else{
                dq.front()-=x;
                if(x!=0&&done){
                    for(ll j=0;j<x;++j){
                        row.push_back(i-dq.size()+1);
                    }
                }
                break;
            }
        }
        if(!row.empty()&&done)v.push_back(row);
    }
    return dq.size()<=d;
}
int main()
{
    // setIO("angry");
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    ll n,d,m;
    cin>>n>>d>>m;
    ll a[n+1];
    memset(a,0,sizeof(a));
    M=vector<vector<ll>>(n+1);
    for(ll i=0;i<m;++i){
        ll x;
        cin>>x;
        M[x].push_back(i+1);
        a[x]++;
    }
    ll l=1,r=m,mid,ans=1e15;
    while(l<=r){
        mid=l+(r-l)/2;
        if(fun(a,n,mid,d,0)){
            ans=mid;
            r=mid-1;
        }
        else{
            l=mid+1;
        }
    }
    fun(a,n,ans,d,1);
    A=v;
    for(ll i=0;i<A.size();++i){
        for(ll j=0;j<A[i].size();++j){
            ll x=A[i][j];
            A[i][j]=M[x].back();
            M[x].pop_back();
        }
        A[i].push_back(0);
    }
    while(A.size()<n){
        A.push_back({0});
    }
    cout<<ans<<endl;
    for(ll i=0;i<n;++i){
        auto it=A[i];
        for(auto it2:it){
            cout<<it2;
            if(it2!=0)
            cout<<" ";
        }
        if(i!=n-1)
        cout<<endl;
    }
    // for(auto it:M){
    //     for(auto it2:it){
    //         cout<<it2<<" ";
    //     }
    //     cout<<endl;
    // }
}

Compilation message

jobs.cpp: In function 'll fun(ll*, ll, ll, ll, ll)':
jobs.cpp:21:21: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
   21 |         if(dq.size()>d)return 0;
      |            ~~~~~~~~~^~
jobs.cpp:47:21: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
   47 |     return dq.size()<=d;
      |            ~~~~~~~~~^~~
jobs.cpp: In function 'int main()':
jobs.cpp:65:24: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '1.0e+15' to '2147483647' [-Woverflow]
   65 |     ll l=1,r=m,mid,ans=1e15;
      |                        ^~~~
jobs.cpp:78:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for(ll i=0;i<A.size();++i){
      |                ~^~~~~~~~~
jobs.cpp:79:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         for(ll j=0;j<A[i].size();++j){
      |                    ~^~~~~~~~~~~~
jobs.cpp:86:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
   86 |     while(A.size()<n){
      |           ~~~~~~~~^~
jobs.cpp: In function 'void setIO(std::string)':
jobs.cpp:11:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |  freopen((s + ".in").c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:12:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |  freopen((s + ".out").c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	3404 KB	Output is correct
2	Correct	16 ms	3468 KB	Output is correct
3	Correct	17 ms	3404 KB	Output is correct
4	Correct	16 ms	3372 KB	Output is correct
5	Correct	16 ms	3404 KB	Output is correct
6	Correct	16 ms	3432 KB	Output is correct
7	Correct	16 ms	3420 KB	Output is correct
8	Correct	18 ms	3376 KB	Output is correct
9	Correct	45 ms	11412 KB	Output is correct
10	Correct	36 ms	11656 KB	Output is correct
11	Correct	16 ms	2708 KB	Output is correct
12	Correct	34 ms	5036 KB	Output is correct
13	Correct	50 ms	8120 KB	Output is correct
14	Correct	76 ms	11368 KB	Output is correct
15	Correct	79 ms	12448 KB	Output is correct
16	Correct	115 ms	15976 KB	Output is correct
17	Correct	128 ms	19240 KB	Output is correct
18	Correct	123 ms	20300 KB	Output is correct
19	Correct	164 ms	29624 KB	Output is correct
20	Correct	129 ms	19156 KB	Output is correct