Submission #986587

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
986587	2024-05-20T20:29:17 Z	kojac	Job Scheduling (CEOI12_jobs)	C++17	95 / 100	772 ms	34716 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;

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

        bool foi = true;
        priority_queue<ll, vector<ll>, greater<ll>> fila;

        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;
    }

    priority_queue<ll, vector<ll>, greater<ll>> fila;
    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:107:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |         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

95.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	54 ms	5060 KB	Output is correct
2	Correct	54 ms	5032 KB	Output is correct
3	Correct	58 ms	4984 KB	Output is correct
4	Correct	54 ms	5012 KB	Output is correct
5	Correct	53 ms	5020 KB	Output is correct
6	Correct	56 ms	5016 KB	Output is correct
7	Correct	58 ms	5064 KB	Output is correct
8	Correct	53 ms	4988 KB	Output is correct
9	Correct	87 ms	6496 KB	Output is correct
10	Correct	83 ms	6500 KB	Output is correct
11	Correct	67 ms	3780 KB	Output is correct
12	Correct	143 ms	7616 KB	Output is correct
13	Correct	217 ms	12344 KB	Output is correct
14	Correct	326 ms	16600 KB	Output is correct
15	Correct	373 ms	17736 KB	Output is correct
16	Correct	524 ms	23452 KB	Output is correct
17	Correct	595 ms	29800 KB	Output is correct
18	Correct	691 ms	29728 KB	Output is correct
19	Runtime error	772 ms	34716 KB	Memory limit exceeded
20	Correct	593 ms	29812 KB	Output is correct