Submission #98863

#	Time	Username	Problem	Language	Result	Execution time	Memory
98863		cfalas	Job Scheduling (CEOI12_jobs)	C++14	10 / 100	1088 ms	17896 KiB

jobs

/*

  ______      _                _____ 
  |  ____/\   | |        /\    / ____|
  | |__ /  \  | |       /  \  | (___  
  |  __/ /\ \ | |      / /\ \  \___ \
  | | / ____ \| |____ / ____ \ ____) |
  |_|/_/    \_\______/_/    \_\_____/ 
                                            
                                            

*/
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define INF 1000000
#define MOD 1000000007

typedef pair<ll, ll> ii;
typedef vector<ll> vi;
typedef pair<ii, ll> iii;
typedef vector<ii> vii;

#define F first
#define S second

#define mp make_pair
#define endl '\n'
#define priority_queue pq

int main(){
    int n, d, m;
    cin>>n>>d>>m;
    vector<vi> pos;
    pos.assign(n+1, vi());
    map<int, int> cnt;
    for(int i=0;i<m;i++){
        int a;
        cin>>a;
        cnt[a]++;
        pos[a].push_back(i+1);
    }

    int l=0;
    int r=m;
    int mid;
    bool moreNeeded = false;
    while(l<=r){
        mid = (l+r-1)/2;
        //cout<<mid<<" "<<l<<" "<<r<<endl;
        moreNeeded = false;
        queue<ii> carry;
        for(int i=1;i<=n;i++){
            carry.push(ii(cnt[i], i));
            if(carry.front().S + d < i){
                moreNeeded = true;
            }
            else{
                ll rms = mid;
                while(rms>0 && !carry.empty()){
                    if(carry.front().F==0){
                        carry.pop();
                    }

                    else{
                        ll qqq = carry.front().F;
                        ll qq = min(rms, qqq);
                        rms -= qq;
                        carry.front().F -= qq;
                    }
                }
            }
        }
        if(moreNeeded){
            l = mid + 1;
            continue;
        }
        else
            r = mid - 1;
    }
    cout<<mid<<endl;
    int cntt = 0;
    queue<int> q;
    for(int i=1;i<=n;i++){
        for(int j=0;j<cnt[i];j++){
            q.push(pos[i][j]);
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=0;j<mid;j++){
            if(!q.empty()){
                cout<<q.front()<<" ";
                q.pop();
            }
        }
        cout<<"0\n";
    }
}

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:83:9: warning: unused variable 'cntt' [-Wunused-variable]
     int cntt = 0;
         ^~~~
jobs.cpp:92:22: warning: 'mid' may be used uninitialized in this function [-Wmaybe-uninitialized]
         for(int j=0;j<mid;j++){
                     ~^~~~

• Subtask 1: 10 / 100