oj.uz

Submission #831902

# Submission time Handle Problem Language Result Execution time Memory
831902 2023-08-20T17:19:28 Z Darren0724 Job Scheduling (CEOI12_jobs) C++17
100 / 100
 242 ms 12148 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;
    for(int i=0;i<n;i++){
        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++){
      |                         ~^~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2128 KB Output is correct
2 Correct 22 ms 2164 KB Output is correct
3 Correct 22 ms 2128 KB Output is correct
4 Correct 22 ms 2200 KB Output is correct
5 Correct 22 ms 2196 KB Output is correct
6 Correct 22 ms 2184 KB Output is correct
7 Correct 22 ms 2128 KB Output is correct
8 Correct 25 ms 2196 KB Output is correct
9 Correct 113 ms 4156 KB Output is correct
10 Correct 114 ms 4096 KB Output is correct
11 Correct 13 ms 1364 KB Output is correct
12 Correct 26 ms 2388 KB Output is correct
13 Correct 42 ms 4688 KB Output is correct
14 Correct 91 ms 7052 KB Output is correct
15 Correct 65 ms 6276 KB Output is correct
16 Correct 105 ms 9488 KB Output is correct
17 Correct 127 ms 12108 KB Output is correct
18 Correct 123 ms 9456 KB Output is correct
19 Correct 242 ms 11716 KB Output is correct
20 Correct 126 ms 12148 KB Output is correct