oj.uz

Submission #831904

# Submission time Handle Problem Language Result Execution time Memory
831904 2023-08-20T17:20:16 Z Darren0724 Job Scheduling (CEOI12_jobs) C++17
100 / 100
 263 ms 18760 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define x first
#define y second
const int mod=1e9+7;


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,d,m;cin>>n>>d>>m;
    vector<int> v[n+1];
    for(int i=1;i<=m;i++){
        int p;cin>>p;
        v[p].push_back(i);
    }
    
    int l=0,r=m;
    while(r-l>1){
        queue<int> q;
        int mi=(l+r)>>1;
        bool flag=0;
        for(int i=1;i<=n;i++){
            for(int j=0;j<v[i].size();j++){
                q.push(i);
            }
            for(int j=0;j<mi;j++){
                if(q.size()==0){
                    break;
                }
                int p=q.front();
                flag|=(i>p+d);
                q.pop();
            }
        }
        //cout<<mi<<(q.size()||flag)<<endl;
        if(q.size()||flag){
            l=mi;
        }
        else{
            r=mi;
        }
    }
    queue<int> q;
    cout<<r<<endl;
    int mi=r;
    vector<int> ptr(n+1);
    int mx=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<v[i].size();j++){
            q.push(i);
        }
        for(int j=0;j<mi;j++){
            if(q.size()==0){
                break;
            }
            int p=q.front();
            mx=max(mx,i-p);
            q.pop();
            cout<<v[p][ptr[p]++]<<' ';
        }
        cout<<0<<endl;
    }
    
    return 0;
}

Compilation message

jobs.cpp: In function 'int32_t main()':
jobs.cpp:25:26: 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]
   25 |             for(int j=0;j<v[i].size();j++){
      |                         ~^~~~~~~~~~~~
jobs.cpp:51:22: 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]
   51 |         for(int j=0;j<v[i].size();j++){
      |                     ~^~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 2836 KB Output is correct
2 Correct 27 ms 2796 KB Output is correct
3 Correct 28 ms 2768 KB Output is correct
4 Correct 27 ms 2844 KB Output is correct
5 Correct 27 ms 2744 KB Output is correct
6 Correct 27 ms 2780 KB Output is correct
7 Correct 27 ms 2868 KB Output is correct
8 Correct 27 ms 2876 KB Output is correct
9 Correct 120 ms 5548 KB Output is correct
10 Correct 118 ms 5528 KB Output is correct
11 Correct 19 ms 2004 KB Output is correct
12 Correct 36 ms 3624 KB Output is correct
13 Correct 53 ms 6672 KB Output is correct
14 Correct 96 ms 8744 KB Output is correct
15 Correct 88 ms 9704 KB Output is correct
16 Correct 139 ms 12372 KB Output is correct
17 Correct 158 ms 15576 KB Output is correct
18 Correct 181 ms 15000 KB Output is correct
19 Correct 263 ms 18760 KB Output is correct
20 Correct 158 ms 15484 KB Output is correct