Submission #98863

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
98863	2019-02-26T20:10:16 Z	cfalas	Job Scheduling (CEOI12_jobs)	C++14	10 / 100	1000 ms	17896 KB

jobs

/*

  ______      _                _____ 
  |  ____/\   | |        /\    / ____|
  | |__ /  \  | |       /  \  | (___  
  |  __/ /\ \ | |      / /\ \  \___ \
  | | / ____ \| |____ / ____ \ ____) |
  |_|/_/    \_\______/_/    \_\_____/ 
                                            
                                            

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

#define ll long long
#define INF 1000000
#define MOD 1000000007

typedef pair<ll, ll> ii;
typedef vector<ll> vi;
typedef pair<ii, ll> iii;
typedef vector<ii> vii;

#define F first
#define S second

#define mp make_pair
#define endl '\n'
#define priority_queue pq

int main(){
    int n, d, m;
    cin>>n>>d>>m;
    vector<vi> pos;
    pos.assign(n+1, vi());
    map<int, int> cnt;
    for(int i=0;i<m;i++){
        int a;
        cin>>a;
        cnt[a]++;
        pos[a].push_back(i+1);
    }

    int l=0;
    int r=m;
    int mid;
    bool moreNeeded = false;
    while(l<=r){
        mid = (l+r-1)/2;
        //cout<<mid<<" "<<l<<" "<<r<<endl;
        moreNeeded = false;
        queue<ii> carry;
        for(int i=1;i<=n;i++){
            carry.push(ii(cnt[i], i));
            if(carry.front().S + d < i){
                moreNeeded = true;
            }
            else{
                ll rms = mid;
                while(rms>0 && !carry.empty()){
                    if(carry.front().F==0){
                        carry.pop();
                    }

                    else{
                        ll qqq = carry.front().F;
                        ll qq = min(rms, qqq);
                        rms -= qq;
                        carry.front().F -= qq;
                    }
                }
            }
        }
        if(moreNeeded){
            l = mid + 1;
            continue;
        }
        else
            r = mid - 1;
    }
    cout<<mid<<endl;
    int cntt = 0;
    queue<int> q;
    for(int i=1;i<=n;i++){
        for(int j=0;j<cnt[i];j++){
            q.push(pos[i][j]);
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=0;j<mid;j++){
            if(!q.empty()){
                cout<<q.front()<<" ";
                q.pop();
            }
        }
        cout<<"0\n";
    }
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:83:9: warning: unused variable 'cntt' [-Wunused-variable]
     int cntt = 0;
         ^~~~
jobs.cpp:92:22: warning: 'mid' may be used uninitialized in this function [-Wmaybe-uninitialized]
         for(int j=0;j<mid;j++){
                     ~^~~~

Subtask #1

10.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1076 ms	2292 KB	Time limit exceeded
2	Execution timed out	1074 ms	2292 KB	Time limit exceeded
3	Execution timed out	1085 ms	2284 KB	Time limit exceeded
4	Execution timed out	1067 ms	2284 KB	Time limit exceeded
5	Execution timed out	1062 ms	2284 KB	Time limit exceeded
6	Execution timed out	1076 ms	2284 KB	Time limit exceeded
7	Execution timed out	1047 ms	2236 KB	Time limit exceeded
8	Execution timed out	1080 ms	2284 KB	Time limit exceeded
9	Correct	647 ms	10296 KB	Output is correct
10	Execution timed out	1077 ms	10476 KB	Time limit exceeded
11	Execution timed out	1088 ms	1916 KB	Time limit exceeded
12	Execution timed out	1076 ms	3064 KB	Time limit exceeded
13	Execution timed out	1071 ms	5368 KB	Time limit exceeded
14	Correct	343 ms	11240 KB	Output is correct
15	Execution timed out	1081 ms	6964 KB	Time limit exceeded
16	Execution timed out	1087 ms	9592 KB	Time limit exceeded
17	Execution timed out	1073 ms	12072 KB	Time limit exceeded
18	Execution timed out	1074 ms	9976 KB	Time limit exceeded
19	Execution timed out	1075 ms	17896 KB	Time limit exceeded
20	Execution timed out	1082 ms	12188 KB	Time limit exceeded