oj.uz

Submission #874497

# Submission time Handle Problem Language Result Execution time Memory
874497 2023-11-17T07:14:44 Z vjudge1 Job Scheduling (CEOI12_jobs) C++17
60 / 100
 361 ms 23588 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++ ;
        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;
    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:38: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]
   38 |     for(int i = 0 ; i < v.size() ; i++){
      |                     ~~^~~~~~~~~~

Subtask #1
60.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 3128 KB Output isn't correct
2 Incorrect 42 ms 3272 KB Output isn't correct
3 Incorrect 39 ms 3112 KB Output isn't correct
4 Incorrect 39 ms 3136 KB Output isn't correct
5 Incorrect 35 ms 3140 KB Output isn't correct
6 Incorrect 39 ms 3124 KB Output isn't correct
7 Incorrect 36 ms 3128 KB Output isn't correct
8 Incorrect 39 ms 3128 KB Output isn't correct
9 Correct 43 ms 3132 KB Output is correct
10 Correct 44 ms 3124 KB Output is correct
11 Correct 42 ms 3156 KB Output is correct
12 Correct 83 ms 5820 KB Output is correct
13 Correct 135 ms 12224 KB Output is correct
14 Correct 161 ms 11000 KB Output is correct
15 Correct 189 ms 12528 KB Output is correct
16 Correct 263 ms 20736 KB Output is correct
17 Correct 294 ms 22040 KB Output is correct
18 Correct 313 ms 22552 KB Output is correct
19 Correct 361 ms 23588 KB Output is correct
20 Correct 297 ms 21676 KB Output is correct