oj.uz

답안 #951632

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
951632 2024-03-22T08:03:35 Z doducanh Job Scheduling (CEOI12_jobs) C++17
100 / 100
 497 ms 30148 KB 
#include <bits/stdc++.h>

using namespace std;
#define ii pair<int,int>
#define fi first
#define se second
const int maxn=1e5+7;
vector<int>a[maxn];
vector<int>ans[maxn];
vector<int>ress[maxn];
int n,d,m;
bool check(int limit)
{
    priority_queue<ii,vector<ii>,greater<ii>>q;
    for(int i=1;i<=n;i++)ans[i].clear();
    for(int i=1;i<=n;i++){
        while(ans[i].size()<limit&&q.size()){
            if(i-q.top().fi>d)return false;
            ans[i].push_back(q.top().se);
            q.pop();
        }
        for(int x:a[i]){
            if(ans[i].size()<limit)ans[i].push_back(x);
            else q.push({i,x});
        }
    }
    if(q.size())return false;
    for(int i=1;i<=n;i++){
        ress[i].clear();
        for(int x:ans[i])ress[i].push_back(x);
    }
    return true;
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>d>>m;
    for(int i=1;i<=m;i++){
        int x;
        cin>>x;
        a[x].push_back(i);
    }
    int l=0,r=m;
    int res=m;
    while(l<=r){
        int m=(l+r)/2;
        if(check(m)){
            res=m;
            r=m-1;
        }
        else l=m+1;
    }
    cout<<res<<"\n";
    for(int i=1;i<=n;i++){
        for(int x:ress[i])cout<<x<<" ";
        cout<<0<<"\n";
    }
    return 0;
}

Compilation message

jobs.cpp: In function 'bool check(int)':
jobs.cpp:17:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   17 |         while(ans[i].size()<limit&&q.size()){
      |               ~~~~~~~~~~~~~^~~~~~
jobs.cpp:23:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   23 |             if(ans[i].size()<limit)ans[i].push_back(x);
      |                ~~~~~~~~~~~~~^~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 10580 KB Output is correct
2 Correct 78 ms 10580 KB Output is correct
3 Correct 71 ms 10576 KB Output is correct
4 Correct 72 ms 10576 KB Output is correct
5 Correct 75 ms 10592 KB Output is correct
6 Correct 73 ms 10576 KB Output is correct
7 Correct 72 ms 10580 KB Output is correct
8 Correct 72 ms 10580 KB Output is correct
9 Correct 45 ms 10064 KB Output is correct
10 Correct 76 ms 10392 KB Output is correct
11 Correct 31 ms 10064 KB Output is correct
12 Correct 152 ms 12344 KB Output is correct
13 Correct 117 ms 16464 KB Output is correct
14 Correct 256 ms 19960 KB Output is correct
15 Correct 90 ms 20780 KB Output is correct
16 Correct 138 ms 24108 KB Output is correct
17 Correct 243 ms 30128 KB Output is correct
18 Correct 497 ms 27648 KB Output is correct
19 Correct 393 ms 28568 KB Output is correct
20 Correct 238 ms 30148 KB Output is correct