제출 #99228

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
99228		cfalas	Job Scheduling (CEOI12_jobs)	C++14	5 / 100	1077 ms	25820 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;
                break;
            }
            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;
                    }
                }
            }*/
        }
        int day = 0;
        ll rms = mid;
        while(day<n && !carry.empty()){
            if(carry.front().F==0){
                carry.pop();
                continue;
            }
            if(rms==0){
                rms = mid;
                day++;
            }
            if(carry.front().S + d < day){
                moreNeeded = true;
                break;
            }
            ll qq = min(rms, carry.front().F);
            rms-=qq;
            carry.front().F -= qq;
            

        }
        if(!carry.empty())
            moreNeeded = true;
        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";
    }
}

컴파일 시 표준 에러 (stderr) 메시지

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

• Subtask 1: 5 / 100