oj.uz

Submission #874483

# Submission time Handle Problem Language Result Execution time Memory
874483 2023-11-17T06:54:11 Z vjudge1 Job Scheduling (CEOI12_jobs) C++17
35 / 100
 490 ms 48736 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++;

    }
    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(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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 5800 KB Output isn't correct
2 Incorrect 52 ms 5880 KB Output isn't correct
3 Incorrect 59 ms 5784 KB Output isn't correct
4 Incorrect 49 ms 5792 KB Output isn't correct
5 Incorrect 48 ms 5824 KB Output isn't correct
6 Incorrect 48 ms 5844 KB Output isn't correct
7 Incorrect 53 ms 5792 KB Output isn't correct
8 Incorrect 42 ms 6152 KB Output isn't correct
9 Correct 55 ms 5812 KB Output is correct
10 Correct 57 ms 5788 KB Output is correct
11 Correct 54 ms 5820 KB Output is correct
12 Correct 91 ms 12048 KB Output is correct
13 Correct 181 ms 19684 KB Output is correct
14 Correct 207 ms 22256 KB Output is correct
15 Correct 244 ms 24356 KB Output is correct
16 Runtime error 346 ms 37664 KB Memory limit exceeded
17 Runtime error 397 ms 40976 KB Memory limit exceeded
18 Runtime error 432 ms 43312 KB Memory limit exceeded
19 Runtime error 490 ms 48736 KB Memory limit exceeded
20 Runtime error 405 ms 41060 KB Memory limit exceeded