oj.uz

답안 #298549

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
298549 2020-09-13T06:11:38 Z Marlov Job Scheduling (CEOI12_jobs) C++14
15 / 100
 1000 ms 25060 KB 
/*
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;
        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+1)/2;
        if(solve(mid)){
            b=mid-1;
        }else{
            a=mid+1;
        }
        //cout<<a<<" "<<mid<<" "<<b<<endl;
    }
    a=b+1;
    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:75: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]
   75 |         for(long long j=0;j<arr[i].size();j++){
      |                           ~^~~~~~~~~~~~~~
jobs.cpp:83: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]
   83 |             if(ci==ans.size()) break;
      |                ~~^~~~~~~~~~~~

Subtask #1
15.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 44 ms 4984 KB Output isn't correct
2 Incorrect 42 ms 4984 KB Output isn't correct
3 Incorrect 42 ms 4984 KB Output isn't correct
4 Incorrect 45 ms 5112 KB Output isn't correct
5 Incorrect 42 ms 4984 KB Output isn't correct
6 Incorrect 42 ms 4984 KB Output isn't correct
7 Incorrect 42 ms 4984 KB Output isn't correct
8 Incorrect 43 ms 4984 KB Output isn't correct
9 Incorrect 272 ms 5756 KB Output isn't correct
10 Incorrect 247 ms 5616 KB Output isn't correct
11 Incorrect 27 ms 5364 KB Output isn't correct
12 Incorrect 44 ms 7656 KB Output isn't correct
13 Incorrect 65 ms 11620 KB Output isn't correct
14 Incorrect 124 ms 13792 KB Output isn't correct
15 Correct 106 ms 16096 KB Output is correct
16 Execution timed out 1054 ms 10488 KB Time limit exceeded
17 Correct 229 ms 23124 KB Output is correct
18 Incorrect 182 ms 23388 KB Output isn't correct
19 Incorrect 397 ms 25060 KB Output isn't correct
20 Correct 200 ms 23252 KB Output is correct