Submission #986590

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
986590	2024-05-20T20:32:07 Z	kojac	Job Scheduling (CEOI12_jobs)	C++17	95 / 100	785 ms	34816 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	56 ms	5032 KB	Output is correct
2	Correct	53 ms	5028 KB	Output is correct
3	Correct	62 ms	5004 KB	Output is correct
4	Correct	53 ms	5064 KB	Output is correct
5	Correct	53 ms	4812 KB	Output is correct
6	Correct	53 ms	4808 KB	Output is correct
7	Correct	63 ms	5008 KB	Output is correct
8	Correct	53 ms	5064 KB	Output is correct
9	Correct	88 ms	6488 KB	Output is correct
10	Correct	83 ms	6496 KB	Output is correct
11	Correct	65 ms	3816 KB	Output is correct
12	Correct	142 ms	7556 KB	Output is correct
13	Correct	218 ms	12332 KB	Output is correct
14	Correct	325 ms	16560 KB	Output is correct
15	Correct	365 ms	17516 KB	Output is correct
16	Correct	500 ms	23620 KB	Output is correct
17	Correct	598 ms	29592 KB	Output is correct
18	Correct	731 ms	29856 KB	Output is correct
19	Runtime error	785 ms	34816 KB	Memory limit exceeded
20	Correct	629 ms	29600 KB	Output is correct