oj.uz

Submission #874500

# Submission time Handle Problem Language Result Execution time Memory
874500 2023-11-17T07:17:19 Z vjudge1 Job Scheduling (CEOI12_jobs) C++17
60 / 100
 397 ms 23788 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--;
        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: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 3136 KB Output isn't correct
2 Incorrect 37 ms 3132 KB Output isn't correct
3 Incorrect 35 ms 3148 KB Output isn't correct
4 Incorrect 34 ms 3168 KB Output isn't correct
5 Incorrect 44 ms 3156 KB Output isn't correct
6 Incorrect 41 ms 3112 KB Output isn't correct
7 Incorrect 35 ms 3124 KB Output isn't correct
8 Incorrect 43 ms 3132 KB Output isn't correct
9 Correct 43 ms 3140 KB Output is correct
10 Correct 42 ms 3144 KB Output is correct
11 Correct 41 ms 3052 KB Output is correct
12 Correct 89 ms 5872 KB Output is correct
13 Correct 140 ms 12164 KB Output is correct
14 Correct 167 ms 10948 KB Output is correct
15 Correct 193 ms 12544 KB Output is correct
16 Correct 295 ms 21516 KB Output is correct
17 Correct 309 ms 22644 KB Output is correct
18 Correct 290 ms 23788 KB Output is correct
19 Correct 397 ms 22952 KB Output is correct
20 Correct 310 ms 23276 KB Output is correct