Submission #986592

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
986592	2024-05-20T20:34:11 Z	kojac	Job Scheduling (CEOI12_jobs)	C++17	90 / 100	837 ms	38220 KB

jobs

// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
 
#include <bits/stdc++.h>
using namespace std;
 
#define F first
#define S second
#define pb push_back
#define endl "\n"
 
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
const ll MAXN = 2e5 + 5;
const ll MOD = 1e9+7;
const ll p = 333;
 
 
int32_t main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL); cout.tie(NULL);
 
    // freopen("angry.in","r",stdin);
    // freopen("angry.out","w",stdout);
 
 
 
 
 
    // int tt; cin >> tt;
 
 
    // while(tt--){
 
    // }
	

   ll n, d, m;
   vector<pll> v;

    cin >> n >> d >> m;

    for(int i = 0; i < m; i++){
        ll x;

        cin >> x;

        v.push_back({x, i+1});
    }

    sort(v.begin(), v.end());


    ll l = 1, r = m, ans;
    
    priority_queue<ll, vector<ll>, greater<ll>> fila;

    while(l <= r){
        ll mid = (l+r)/2;

        bool foi = true;

        while(!fila.empty())fila.pop();
        

        for(int i = 0; i < mid; i++) fila.push(v[i].F+1);

        for(int i = mid; i < m; i++){
            ll aux = fila.top();
            fila.pop();
            if(aux-v[i].F > d){
                foi = false;
                break;
            }else{
                fila.push(max(aux,v[i].F)+1);
            }

        }

        if(foi){
            ans = mid;
            r = mid-1;
        }else l = mid+1;
    }

    while(!fila.empty()) fila.pop();
    vector<ll> resp[n+5];

    for(int i = 0; i < ans; i++){
        fila.push(v[i].F+1);
        resp[v[i].F].push_back(v[i].S);
    }

    for(int i = ans; i < m; i++){
        ll aux = fila.top();
        fila.pop();

        fila.push(max(aux,v[i].F)+1);

        resp[max(aux,v[i].F)].push_back(v[i].S);
    }

    cout << ans << endl;

    for(int i = 1; i <= n; i++){
        for(int j = 0; j < resp[i].size(); j++){
            cout << resp[i][j] << " ";
        }

        cout << "0\n";
    }
 
   

    
 
	
 
    
    
    return 0;
}

Compilation message

jobs.cpp: In function 'int32_t main()':
jobs.cpp:111:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |         for(int j = 0; j < resp[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~~
jobs.cpp:59:22: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   59 |     ll l = 1, r = m, ans;
      |                      ^~~

Subtask #1

90.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	64 ms	4812 KB	Output is correct
2	Correct	65 ms	4752 KB	Output is correct
3	Correct	66 ms	4752 KB	Output is correct
4	Correct	66 ms	4732 KB	Output is correct
5	Correct	64 ms	4808 KB	Output is correct
6	Correct	63 ms	4756 KB	Output is correct
7	Correct	66 ms	4808 KB	Output is correct
8	Correct	65 ms	4808 KB	Output is correct
9	Correct	88 ms	6904 KB	Output is correct
10	Correct	85 ms	6880 KB	Output is correct
11	Correct	72 ms	4300 KB	Output is correct
12	Correct	152 ms	8460 KB	Output is correct
13	Correct	236 ms	13352 KB	Output is correct
14	Correct	354 ms	18168 KB	Output is correct
15	Correct	396 ms	19376 KB	Output is correct
16	Correct	544 ms	24388 KB	Output is correct
17	Correct	644 ms	32548 KB	Output is correct
18	Runtime error	747 ms	33048 KB	Memory limit exceeded
19	Runtime error	837 ms	38220 KB	Memory limit exceeded
20	Correct	652 ms	32412 KB	Output is correct