oj.uz

Submission #874501

# Submission time Handle Problem Language Result Execution time Memory
874501 2023-11-17T07:18:07 Z vjudge1 Job Scheduling (CEOI12_jobs) C++17
100 / 100
 339 ms 24792 KB 
//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++ , i--;
            continue;
        }
        flag++;
        if(flag == mid) flag = 0 , cnt++;

    }
    if(flag == 0) cnt--;
    if(cnt > n) return false;
    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+100;
    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

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

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 3140 KB Output is correct
2 Correct 32 ms 3124 KB Output is correct
3 Correct 32 ms 3136 KB Output is correct
4 Correct 32 ms 3128 KB Output is correct
5 Correct 40 ms 3068 KB Output is correct
6 Correct 33 ms 3128 KB Output is correct
7 Correct 33 ms 3108 KB Output is correct
8 Correct 32 ms 3120 KB Output is correct
9 Correct 41 ms 3136 KB Output is correct
10 Correct 40 ms 3140 KB Output is correct
11 Correct 39 ms 3128 KB Output is correct
12 Correct 79 ms 5784 KB Output is correct
13 Correct 122 ms 9928 KB Output is correct
14 Correct 177 ms 11036 KB Output is correct
15 Correct 200 ms 12688 KB Output is correct
16 Correct 260 ms 20796 KB Output is correct
17 Correct 309 ms 20396 KB Output is correct
18 Correct 327 ms 24792 KB Output is correct
19 Correct 339 ms 23812 KB Output is correct
20 Correct 283 ms 21504 KB Output is correct