Submission #986598

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
986598	2024-05-20T20:39:15 Z	kojac	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	818 ms	25472 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--){
 
    // }
	

   int n, d, m;
   vector<pii> v;

    cin >> n >> d >> m;

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

        cin >> x;

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

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


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

    while(l <= r){
        int 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++){
            int 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<int> 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++){
        int 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<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |         for(int j = 0; j < resp[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~~
jobs.cpp:59:23: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   59 |     int l = 1, r = m, ans;
      |                       ^~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	66 ms	3016 KB	Output is correct
2	Correct	64 ms	3024 KB	Output is correct
3	Correct	65 ms	3000 KB	Output is correct
4	Correct	65 ms	3004 KB	Output is correct
5	Correct	81 ms	3016 KB	Output is correct
6	Correct	64 ms	3116 KB	Output is correct
7	Correct	68 ms	3020 KB	Output is correct
8	Correct	72 ms	3012 KB	Output is correct
9	Correct	90 ms	5212 KB	Output is correct
10	Correct	93 ms	5352 KB	Output is correct
11	Correct	71 ms	2840 KB	Output is correct
12	Correct	174 ms	5344 KB	Output is correct
13	Correct	247 ms	8384 KB	Output is correct
14	Correct	354 ms	11656 KB	Output is correct
15	Correct	401 ms	12672 KB	Output is correct
16	Correct	531 ms	16104 KB	Output is correct
17	Correct	669 ms	20576 KB	Output is correct
18	Correct	738 ms	21056 KB	Output is correct
19	Correct	818 ms	25472 KB	Output is correct
20	Correct	628 ms	20672 KB	Output is correct