Submission #874483

#	Time	Username	Problem	Language	Result	Execution time	Memory
874483		vjudge1	Job Scheduling (CEOI12_jobs)	C++17	35 / 100	490 ms	48736 KiB

jobs

//In His Name
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
typedef pair<int, int> pii;
typedef pair<long long, int> pli;
typedef pair<long long, long long> pll;
#define F first
#define S second
#define pb push_back
#define bug(x) cout << "Ah shit , here we go again : " << x <<endl
#define all(x) x.begin() , x.end()
#define ceil(x,y) x/y + min(1ll,x%y)
const int maxn = 5e3 + 10, MOD = 1e9 + 7;
const ll INF = 1e18;

int n , d , m;
vector<pii> v;
bool check(int mid){
    vector<pii> s;
    for(pii i : v) s.pb(i);
    int cnt = 1 , flag = 0;
    for(int i = 0 ; i < s.size(); i++){
        if(cnt - s[i].F > d) return false;
        if(cnt < s[i].F) flag = 0 , cnt++ ;
        flag++;
        if(flag == mid) flag = 0 , cnt++;

    }
    return true;
}

void Find_Ans(int x){
    int cnt = 1 , flag = 0;
    for(int i = 0 ; i < v.size() ; i++){
        if(cnt < v[i].F) flag = 0 , cnt++ , cout << 0 << "\n";
        cout << v[i].S << " ";
        flag ++;
        if(flag == x) flag = 0 , cnt++ , cout << 0 << "\n";
    }
    for( ; cnt <= n ; cnt++) cout << "0\n";
}

signed main(){
    ios_base::sync_with_stdio(false);

    cin >> n >> d >> m;
    for(int i = 1 ; i <= m ; i++){
        int x;
        cin >> x;
        v.pb({x,i});
    }
    sort(all(v));
    int l = 1 , r = 1e9;
    while(r - l > 1){
        int mid = (l+r) >> 1;
        if(check(mid)) r = mid;
        else l = mid;
    }
    cout << r << "\n";
    Find_Ans(r);

}

Compilation message (stderr)

jobs.cpp: In function 'bool check(long long int)':
jobs.cpp:24:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i = 0 ; i < s.size(); i++){
      |                     ~~^~~~~~~~~~
jobs.cpp: In function 'void Find_Ans(long long int)':
jobs.cpp:36:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(int i = 0 ; i < v.size() ; i++){
      |                     ~~^~~~~~~~~~

• Subtask 1: 35 / 100