Submission #553334

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
553334	2022-04-25T13:31:56 Z	Soul234	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	278 ms	14976 KB

jobs

#include<bits/stdc++.h>
using namespace std;

void DBG() { cerr << "]\n"; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << h; if(sizeof...(t)) cerr << ", ";
    DBG(t...);
}
#ifdef LOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif // LOCAL

#define FOR(i,a,b) for(int i = (a) ; i<(b) ; i++)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for(int i = (b)-1 ; i>=(a) ; i--)
#define R0F(i,a) ROF(i,0,a)
#define each(e,a) for(auto &e : (a))
#define sz(v) (int)(v).size()
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pb push_back
#define tcT template<class T
#define nl "\n"

using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;
using str = string;
tcT> using V = vector<T>;
tcT> using pqg = priority_queue<T,vector<T>,greater<T>>;

void setIO(string NAME = "") {
    cin.tie(0)->sync_with_stdio(0);
    if(sz(NAME)) {
        freopen((NAME + ".in").c_str(),"r",stdin);
        freopen((NAME + ".out").c_str(),"w",stdout);
    }
}

const int MX = 1e6+5;
int N, D, M;
array<int,2> A[MX];

bool ok(int x, bool prans = false) {
    int pt = 0;
    FOR(d,1,N+1) {
        F0R(_,x) {
            if(pt>=M || A[pt][0] > d) break;
            if(A[pt][0]+D >= d) {
                assert(A[pt][0] <= d);
                if(prans) cout << A[pt++][1]+1 << " ";
                else pt++;
            }
            else return false;
        }
        if(prans) cout << "0\n";
    }
    return true;
}

void solve() {
    cin>>N>>D>>M;
    F0R(i,M) {
        cin>>A[i][0];
        A[i][1] = i;
    }
    sort(A,A+M);
    int lo = 0, hi = M+1;
    while(lo<hi) {
        int mid = lo + (hi-lo)/2;
        if(ok(mid)) hi = mid;
        else lo = mid+1;
    }
    cout << lo << nl;
    ok(lo, true);
}

int main() {
    setIO();

    int t=1;
    //cin>>t;
    while(t-->0) {
        solve();
    }

    return 0;
}

Compilation message

jobs.cpp: In function 'void setIO(std::string)':
jobs.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         freopen((NAME + ".in").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         freopen((NAME + ".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	2004 KB	Output is correct
2	Correct	23 ms	2116 KB	Output is correct
3	Correct	28 ms	1924 KB	Output is correct
4	Correct	23 ms	1996 KB	Output is correct
5	Correct	21 ms	1988 KB	Output is correct
6	Correct	21 ms	1908 KB	Output is correct
7	Correct	21 ms	1884 KB	Output is correct
8	Correct	22 ms	1996 KB	Output is correct
9	Correct	30 ms	2124 KB	Output is correct
10	Correct	35 ms	2108 KB	Output is correct
11	Correct	29 ms	1984 KB	Output is correct
12	Correct	58 ms	3788 KB	Output is correct
13	Correct	91 ms	5192 KB	Output is correct
14	Correct	129 ms	6892 KB	Output is correct
15	Correct	158 ms	8172 KB	Output is correct
16	Correct	193 ms	9876 KB	Output is correct
17	Correct	241 ms	11736 KB	Output is correct
18	Correct	253 ms	13036 KB	Output is correct
19	Correct	278 ms	14976 KB	Output is correct
20	Correct	233 ms	11816 KB	Output is correct