Submission #559214

#	Time	Username	Problem	Language	Result	Execution time	Memory
559214		Cookie	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	247 ms	13864 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
#define LIFESUCKS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define ld long double
#define ar array
#include<cstdio>
#define vt vector
#include<fstream>
ifstream fin("measurement.in");
ofstream fout("measurement.out");
#include<fstream>
#define pb push_back
#define all(c) (c).begin(), (c).end()
//#define length(x) (int)(x).size()
#define fi first
#define se second
#define vt vector
using namespace std;
int n, d, m;
const int mxm = 1e6;
vt<pair<int, int>>p;
bool check(int mid){
    int cr;
    int make = 0;
    
    for(int i = 1; i <= n; i++){
        cr = 0;
        
        while(make < m && p[make].first <= i && cr < mid){
            if(p[make].first + d < i)return(false);
            make++;
            cr++;
        }
    }
    return(make == m);
}
int main()
{
   LIFESUCKS;
   cin >> n >> d >> m;
   for(int i = 0; i < m; i++){
       int x; cin >> x;
       p.pb({x, i + 1});
   }
   sort(p.begin(), p.end());
   int l = 1;
   int ans = -1;
   int r = m;
   while(l <= r){
       int mid = l + (r - l) / 2;
       if(check(mid)){
           ans = mid; r = mid - 1;
       }else{
           l = mid + 1;
       }
   }
   cout << ans << "\n";
   int cr;
    int make = 0;
   for(int i = 1; i <= n; i++){
       cr = 0;
       while(make < m && p[make].first <= i && cr < ans){
           
           cout << p[make].second << " ";
           make++;
           cr++;
       }
       cout << 0 << "\n";
   }
   //for(int i = cr; i < n; i++)cout << 0 << "\n";
   
   return 0;
}

• Subtask 1: 100 / 100