oj.uz

Submission #831900

# Submission time Handle Problem Language Result Execution time Memory
831900 2023-08-20T17:18:32 Z Darren0724 Job Scheduling (CEOI12_jobs) C++17
40 / 100
 246 ms 20412 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=2;
    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
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 23 ms 2328 KB Partially correct
2 Partially correct 23 ms 2296 KB Partially correct
3 Partially correct 28 ms 2384 KB Partially correct
4 Partially correct 23 ms 2376 KB Partially correct
5 Partially correct 23 ms 2268 KB Partially correct
6 Partially correct 23 ms 2288 KB Partially correct
7 Partially correct 23 ms 2268 KB Partially correct
8 Partially correct 23 ms 2256 KB Partially correct
9 Partially correct 120 ms 6004 KB Partially correct
10 Partially correct 135 ms 6144 KB Partially correct
11 Partially correct 13 ms 2116 KB Partially correct
12 Partially correct 27 ms 3820 KB Partially correct
13 Partially correct 38 ms 6860 KB Partially correct
14 Partially correct 74 ms 8968 KB Partially correct
15 Partially correct 62 ms 9708 KB Partially correct
16 Partially correct 115 ms 12520 KB Partially correct
17 Partially correct 123 ms 15648 KB Partially correct
18 Partially correct 114 ms 15332 KB Partially correct
19 Partially correct 246 ms 20412 KB Partially correct
20 Partially correct 124 ms 15540 KB Partially correct