oj.uz

Submission #951617

# Submission time Handle Problem Language Result Execution time Memory
951617 2024-03-22T07:38:38 Z doducanh Job Scheduling (CEOI12_jobs) C++14
0 / 100
 977 ms 32592 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()
{
    cin>>n>>d>>m;
    for(int i=1;i<=m;i++){
        int x;
        cin>>x;
        a[x].push_back(i);
    }
    int l=0,r=1e6+7;
    int res=r;
    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 176 ms 12340 KB Expected EOLN
2 Incorrect 174 ms 12344 KB Expected EOLN
3 Incorrect 177 ms 12340 KB Expected EOLN
4 Incorrect 179 ms 12304 KB Expected EOLN
5 Incorrect 173 ms 12344 KB Expected EOLN
6 Incorrect 172 ms 12304 KB Expected EOLN
7 Incorrect 183 ms 12544 KB Expected EOLN
8 Incorrect 173 ms 12296 KB Expected EOLN
9 Incorrect 153 ms 13320 KB Expected EOLN
10 Incorrect 167 ms 13640 KB Expected EOLN
11 Incorrect 85 ms 10064 KB Expected EOLN
12 Incorrect 256 ms 12736 KB Expected EOLN
13 Incorrect 331 ms 16724 KB Expected EOLN
14 Incorrect 434 ms 20204 KB Expected EOLN
15 Incorrect 490 ms 21620 KB Expected EOLN
16 Incorrect 475 ms 25428 KB Expected EOLN
17 Incorrect 662 ms 31316 KB Expected EOLN
18 Incorrect 977 ms 28896 KB Expected EOLN
19 Incorrect 966 ms 32592 KB Expected EOLN
20 Incorrect 651 ms 31632 KB Expected EOLN