답안 #298550

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
298550	2020-09-13T06:14:00 Z	Marlov	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	400 ms	25316 KB

jobs

/*
Code by @marlov       
*/
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <utility>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <iterator>
using namespace std;
typedef long long ll;
typedef pair<long long,long long> pi;
 
 
#define maxN 100005
 
long long N,D,M;
vector<long long> arr[maxN];
vector<long long> ans;
bool solve(long long num){
    priority_queue< pair<long long,long long> , vector< pair<long long,long long> > , greater< pair<long long,long long> > > pq;
    for(long long i=0;i<N;i++){
        long long cc=num;
        if(arr[i].size()>0) pq.push(make_pair(i,arr[i].size()));
        while(!pq.empty()&&cc>0){
            if(pq.top().first<i-D) return false;
            if(pq.top().second<=cc){
                cc-=pq.top().second;
                pq.pop();
            }else if(pq.top().second>cc){
                pair<long long,long long> cur=pq.top();pq.pop();
                cur.second-=cc;
                pq.push(cur);
                cc=0;
            }
        }
    }
    if(pq.size()>0) return false;
    return true;
}
 
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N>>D>>M;
    long long num;
    for(long long i=0;i<M;i++){
        cin>>num;
        num--;
        arr[num].push_back(i);
    }
    long long a=0;
    long long b=1000000;
    while(a<b){
        long long mid=(a+b)/2;
        if(solve(mid)){
            b=mid;
        }else{
            a=mid+1;
        }
        //cout<<a<<" "<<mid<<" "<<b<<endl;
    }
    for(long long i=0;i<N;i++){
        for(long long j=0;j<arr[i].size();j++){
            ans.push_back(arr[i][j]);
        }
    }
    cout<<a<<'\n';
    long long ci=0;
    for(long long i=0;i<N;i++){
        for(long long j=0;j<a;j++){
            if(ci==ans.size()) break;
            cout<<ans[ci]+1<<" ";
            ci++;
        }
        cout<<0<<endl;
    }
    return 0;
}
 
/* stuff you should look for
	* long long overflow, array bounds
	* special cases (n=1,n=0?)
	* do smth instead of nothing and stay organized
*/

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:74:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         for(long long j=0;j<arr[i].size();j++){
      |                           ~^~~~~~~~~~~~~~
jobs.cpp:82:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |             if(ci==ans.size()) break;
      |                ~~^~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	41 ms	4984 KB	Output is correct
2	Correct	42 ms	4984 KB	Output is correct
3	Correct	41 ms	5112 KB	Output is correct
4	Correct	44 ms	5112 KB	Output is correct
5	Correct	43 ms	4984 KB	Output is correct
6	Correct	42 ms	5112 KB	Output is correct
7	Correct	42 ms	4984 KB	Output is correct
8	Correct	45 ms	5112 KB	Output is correct
9	Correct	246 ms	5736 KB	Output is correct
10	Correct	236 ms	5616 KB	Output is correct
11	Correct	25 ms	5364 KB	Output is correct
12	Correct	44 ms	7652 KB	Output is correct
13	Correct	65 ms	11628 KB	Output is correct
14	Correct	124 ms	13668 KB	Output is correct
15	Correct	101 ms	16224 KB	Output is correct
16	Correct	172 ms	19288 KB	Output is correct
17	Correct	206 ms	23280 KB	Output is correct
18	Correct	185 ms	23388 KB	Output is correct
19	Correct	400 ms	25316 KB	Output is correct
20	Correct	208 ms	23252 KB	Output is correct