oj.uz

Submission #951623

# Submission time Handle Problem Language Result Execution time Memory
951623 2024-03-22T07:50:30 Z doducanh Job Scheduling (CEOI12_jobs) C++14
0 / 100
 1000 ms 29284 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 x)
{
    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++){

        for(int x:a[i])q.push({i,x});
        while(ans[i].size()<x&&q.size()){
            if(i-q.top().fi>d)return false;
            ans[i].push_back(q.top().se);
            q.pop();
        }
    }
    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);
        ress[i].push_back(0);
    }
    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<<"\n";
    }
    return 0;
}

Compilation message

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

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 148 ms 11148 KB Expected EOLN
2 Incorrect 143 ms 10836 KB Expected EOLN
3 Incorrect 145 ms 10824 KB Expected EOLN
4 Incorrect 144 ms 10840 KB Expected EOLN
5 Incorrect 147 ms 10832 KB Expected EOLN
6 Incorrect 150 ms 10824 KB Expected EOLN
7 Incorrect 144 ms 10856 KB Expected EOLN
8 Incorrect 147 ms 10980 KB Expected EOLN
9 Incorrect 120 ms 13508 KB Expected EOLN
10 Incorrect 124 ms 13260 KB Expected EOLN
11 Incorrect 72 ms 9624 KB Expected EOLN
12 Incorrect 232 ms 11952 KB Expected EOLN
13 Incorrect 279 ms 15700 KB Expected EOLN
14 Incorrect 368 ms 18888 KB Expected EOLN
15 Incorrect 404 ms 19792 KB Expected EOLN
16 Incorrect 347 ms 22172 KB Expected EOLN
17 Incorrect 527 ms 28168 KB Expected EOLN
18 Incorrect 974 ms 25924 KB Expected EOLN
19 Execution timed out 1000 ms 29284 KB Time limit exceeded
20 Incorrect 524 ms 28044 KB Expected EOLN