oj.uz

Submission #589597

# Submission time Handle Problem Language Result Execution time Memory
589597 2022-07-04T22:13:13 Z Metal_Sonic Job Scheduling (CEOI12_jobs) C++17
100 / 100
 409 ms 29812 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sz(x) (int)(x).size()
#define all(x) x.begin() , x.end()
void Sonic(string name = "") {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    if(sz(name)){
        freopen((name+".in").c_str(), "r", stdin);
        freopen((name+".out").c_str(), "w", stdout);
    }
}
int n,d,jobs;
vector<pair<int,int>>vi;
pair<bool,vector<vector<int>>>check(int lim){
    vector<vector<int>>tmp(n);
    int cnt = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < lim; j++){
            if(vi[cnt].first > i)break;
            if(vi[cnt].first + d >= i)
                tmp[i-1].push_back(vi[cnt++].second);
            else return {false,tmp};
            if(cnt==jobs) return {true,tmp};
        }
    }
    return {false,tmp};
}
void run_test_case(){
    cin>>n>>d>>jobs;
    for(int i = 0; i < jobs; i++){
        int x;cin>>x;
        vi.emplace_back(x,i+1);
    }
    sort(all(vi));
    int l = 1, r = jobs;
    vector<vector<int>>ans;
    while(l<r){
        int mid = l + (r-l)/2;
        pair<bool,vector<vector<int>>>p = check(mid);
        if(p.first){
            r = mid;
            ans = p.second;
        }else l = mid+1;
    }
    cout<<l<<'\n';
    for(int i = 0; i < n; i++){
        for(int &it : ans[i])cout<<it<<" ";
        cout<<"0\n";
    }
}
int main(){
    Sonic();
    int T = 1;
    while(T--){
        run_test_case();
    }
    return 0;
}

Compilation message

jobs.cpp: In function 'void Sonic(std::string)':
jobs.cpp:9:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |         freopen((name+".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:10:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         freopen((name+".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3364 KB Output is correct
2 Correct 30 ms 3324 KB Output is correct
3 Correct 28 ms 3280 KB Output is correct
4 Correct 30 ms 3336 KB Output is correct
5 Correct 27 ms 3348 KB Output is correct
6 Correct 28 ms 3324 KB Output is correct
7 Correct 29 ms 3320 KB Output is correct
8 Correct 30 ms 3336 KB Output is correct
9 Correct 76 ms 9972 KB Output is correct
10 Correct 81 ms 9920 KB Output is correct
11 Correct 35 ms 3548 KB Output is correct
12 Correct 70 ms 6864 KB Output is correct
13 Correct 104 ms 10552 KB Output is correct
14 Correct 186 ms 15268 KB Output is correct
15 Correct 186 ms 15908 KB Output is correct
16 Correct 237 ms 21292 KB Output is correct
17 Correct 290 ms 26112 KB Output is correct
18 Correct 289 ms 26928 KB Output is correct
19 Correct 409 ms 29812 KB Output is correct
20 Correct 307 ms 26280 KB Output is correct