Submission #554227

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
554227	2022-04-28T03:27:19 Z	wyhong3103	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	255 ms	17176 KB

jobs

#include <bits/stdc++.h>
#include <limits>
#define all(x) begin(x),end(x)
#define fir first
#define sec second
#define sz(x) x.size()
#define pb push_back
 
using namespace std;
using vi = vector<int>;
using pi = pair<int,int>;
using ll = long long;
const double EPS = (1e-7);
 
void setio(string s){
	freopen((s + ".in").c_str(),"r",stdin);
	freopen((s + ".out").c_str(),"w",stdout);
}
 
bool valid(vector<pi>& a, int mid, int d, int n){
    int day = 1;
    int cur = 0;
    for(auto& i : a){
        if ((day-i.fir) >  d || day > n){
            return false;
        }
        if (i.fir > day){
            day = i.fir;
            cur = 1;
        }else{
            cur++;
        }
        if (cur == mid){
            cur = 0;
            day++;
        }
    }
    return true;
}
 
 
void solve(){
    int n, d, m;
    cin >> n >> d >> m;
 
    vector<pi> a(m);
    for(int i{}; i < m; i++){
        cin >> a[i].fir;
        a[i].sec = i+1;
    }
 
    sort(all(a));
 
    int lo = 1, hi = m;
    while (hi > lo){
        int mid = lo + (hi-lo)/2;
        if (valid(a, mid, d, n)){
            hi = mid;
        }else{
            lo = mid+1;
        }
    }
 
    cout << lo << '\n';
    int p = 0;
    for(int i{}; i < n; i++){
        for(int j{}; j < lo; j++){
            if (p < sz(a) && a[p].fir <= i+1){
                cout << a[p].sec << ' ';
                p++;
            }else break;
        }
        cout << 0 << '\n';
    }
}
 
 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	solve();
	return 0;
}

Compilation message

jobs.cpp: In function 'void solve()':
jobs.cpp:68:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |             if (p < sz(a) && a[p].fir <= i+1){
      |                   ^
jobs.cpp: In function 'void setio(std::string)':
jobs.cpp:16:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |  freopen((s + ".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:17:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |  freopen((s + ".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	1952 KB	Output is correct
2	Correct	19 ms	1912 KB	Output is correct
3	Correct	18 ms	1996 KB	Output is correct
4	Correct	18 ms	1996 KB	Output is correct
5	Correct	19 ms	1988 KB	Output is correct
6	Correct	18 ms	1996 KB	Output is correct
7	Correct	19 ms	2004 KB	Output is correct
8	Correct	18 ms	2020 KB	Output is correct
9	Correct	30 ms	2132 KB	Output is correct
10	Correct	31 ms	2136 KB	Output is correct
11	Correct	27 ms	2028 KB	Output is correct
12	Correct	55 ms	3924 KB	Output is correct
13	Correct	79 ms	5724 KB	Output is correct
14	Correct	110 ms	8172 KB	Output is correct
15	Correct	130 ms	9456 KB	Output is correct
16	Correct	162 ms	11972 KB	Output is correct
17	Correct	192 ms	13848 KB	Output is correct
18	Correct	210 ms	15052 KB	Output is correct
19	Correct	255 ms	17176 KB	Output is correct
20	Correct	194 ms	13964 KB	Output is correct