Submission #117207

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
117207	2019-06-15T11:08:52 Z	JohnTitor	Job Scheduling (CEOI12_jobs)	C++11	100 / 100	119 ms	16632 KB

jobs

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
#define __builtin_popcount __builtin_popcountll
using ll=long long; using ld=long double;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const ld pi=acos(0)*2;
template <typename T> inline void read(T &x){char c; bool nega=0; while((!isdigit(c=getchar()))&&(c!='-')); if(c=='-'){nega=1; c=getchar();} x=c-48; while(isdigit(c=getchar())) x=x*10+c-48; if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10); putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){ putchar('-'); x=-x;} writep(x);}
template <typename T> inline void writeln(T x){write(x); putchar('\n');}
#define taskname "Jobs"
int n;
int d;
int m;
vector <int> f[100001];
deque <int> q;
bool test(int mx){
    q.clear();
    FOR(i, 1, n){
        q.pb(f[i].size());
        int w=mx;
        while(w&&(!q.empty())){
            int d=min(q.front(), w);
            q.front()-=d;
            w-=d;
            while((!q.empty())&&(q.front()==0)) q.pop_front();
        }
        if(q.size()>d) return 0;
    }
    return 1;
}
void output(int mx){
    q.clear();
    FOR(i, 1, n){
        for(int x: f[i]) q.pb(x);
        int w=mx;
        while(w&&(!q.empty())){
            write(q.front());
            putchar(' ');
            q.pop_front();
            w--;
        }
        puts("0");
    }
}
int main(){
    #ifdef Aria
        if(fopen(taskname".in", "r"))
            freopen(taskname".in", "r", stdin);
    #endif // Aria
    read(n);
    read(d);
    read(m);
    FOR(i, 1, m){
        int x;
        read(x);
        f[x].pb(i);
    }
    int low=1, high=m, mid, res;
    while(low<=high){
        mid=(low+high)/2;
        if(test(mid)){
            res=mid;
            high=mid-1;
        }
        else low=mid+1;
    }
    writeln(res);
    output(res);
}

Compilation message

jobs.cpp: In function 'bool test(int)':
jobs.cpp:36:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(q.size()>d) return 0;
            ~~~~~~~~^~
jobs.cpp: In function 'int main()':
jobs.cpp:17:69: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
 template <typename T> inline void write(T x){if(x<0){ putchar('-'); x=-x;} writep(x);}
                                                                     ^
jobs.cpp:67:29: note: 'res' was declared here
     int low=1, high=m, mid, res;
                             ^~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	4472 KB	Output is correct
2	Correct	14 ms	4472 KB	Output is correct
3	Correct	14 ms	4344 KB	Output is correct
4	Correct	14 ms	4344 KB	Output is correct
5	Correct	14 ms	4344 KB	Output is correct
6	Correct	14 ms	4344 KB	Output is correct
7	Correct	14 ms	4344 KB	Output is correct
8	Correct	14 ms	4344 KB	Output is correct
9	Correct	22 ms	4216 KB	Output is correct
10	Correct	22 ms	4352 KB	Output is correct
11	Correct	15 ms	4224 KB	Output is correct
12	Correct	26 ms	5760 KB	Output is correct
13	Correct	38 ms	7880 KB	Output is correct
14	Correct	66 ms	9976 KB	Output is correct
15	Correct	59 ms	10836 KB	Output is correct
16	Correct	106 ms	13432 KB	Output is correct
17	Correct	119 ms	15864 KB	Output is correct
18	Correct	108 ms	15416 KB	Output is correct
19	Correct	116 ms	16632 KB	Output is correct
20	Correct	118 ms	15992 KB	Output is correct