Submission #559214

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
559214	2022-05-09T13:44:21 Z	Cookie	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	247 ms	13864 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	1872 KB	Output is correct
2	Correct	21 ms	1872 KB	Output is correct
3	Correct	24 ms	1836 KB	Output is correct
4	Correct	26 ms	1872 KB	Output is correct
5	Correct	19 ms	1872 KB	Output is correct
6	Correct	26 ms	1836 KB	Output is correct
7	Correct	18 ms	1804 KB	Output is correct
8	Correct	18 ms	1872 KB	Output is correct
9	Correct	34 ms	1988 KB	Output is correct
10	Correct	45 ms	1956 KB	Output is correct
11	Correct	35 ms	1784 KB	Output is correct
12	Correct	53 ms	3264 KB	Output is correct
13	Correct	79 ms	4724 KB	Output is correct
14	Correct	113 ms	6276 KB	Output is correct
15	Correct	134 ms	7648 KB	Output is correct
16	Correct	159 ms	9200 KB	Output is correct
17	Correct	234 ms	10680 KB	Output is correct
18	Correct	220 ms	12220 KB	Output is correct
19	Correct	247 ms	13864 KB	Output is correct
20	Correct	201 ms	10720 KB	Output is correct