oj.uz

답안 #744011

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
744011 2023-05-18T07:11:55 Z vjudge1 Job Scheduling (CEOI12_jobs) C++17
55 / 100
 230 ms 28032 KB 
#include<bits/stdc++.h>
using namespace std;

#define ll unsigned long long
const int N = 1e5+1;
ll n,d,m;

struct job
{
    ll dline,give,idx;

    bool operator <(const job &x)const{
        if(give != x.give) give < x.give;
        return dline < x.dline;
    }
};

ll ans;
vector<job> vec;
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> d >> m;
    for(int i=1;i<=m;++i)
    {
        ll x;
        cin >> x;
        vec.push_back({x+d,x,i});
    }
    sort(vec.begin(),vec.end());
//    while(!pq.empty())
//    {
//        cout << pq.top().dline << " " << pq.top().idx << '\n';
//        pq.pop();
//    }
    ll l = 1,r = 1e9+7;
    while(l<=r)
    {
        ll mid=(l+r)/2;
        ll day=1,cb = 0;
        bool can = true;
//        cout << "mid = " << mid << '\n';
        for(int i=0;i<m;++i)
        {
            ll num = day;
//            cout << "day : " << num << " this job death line : " << vec[i].dline << '\n';
            if(day > vec[i].dline)
            {
                can = false;
                break;
            }
            ++cb;
            if(cb == mid)
            {
                ++day;
                cb = 0;
            }
        }
        if(can)
        {
            ans = mid;
            r = mid-1;
        }
        else l = mid+1;
//        cout << "\n\n";
    }
    cout << ans << '\n';
    ll cnt = 0;
    for(int i=0;i<m;++i)
    {
        if(vec[i].dline != 0) cout << vec[i].idx << " ";
        if((i+1)%ans == 0)
        {
            cout << "0\n";
            ++cnt;
        }
    }
    while(cnt < n)
    {
        cout << "0\n";
        cnt++;
    }
    return 0;
}

Compilation message

jobs.cpp: In member function 'bool job::operator<(const job&) const':
jobs.cpp:13:33: warning: statement has no effect [-Wunused-value]
   13 |         if(give != x.give) give < x.give;
      |                            ~~~~~^~~~~~~~
jobs.cpp: In function 'int main()':
jobs.cpp:24:18: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
   24 |     for(int i=1;i<=m;++i)
      |                 ~^~~
jobs.cpp:28:30: warning: narrowing conversion of 'i' from 'int' to 'long long unsigned int' [-Wnarrowing]
   28 |         vec.push_back({x+d,x,i});
      |                              ^
jobs.cpp:43:22: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
   43 |         for(int i=0;i<m;++i)
      |                     ~^~
jobs.cpp:45:16: warning: unused variable 'num' [-Wunused-variable]
   45 |             ll num = day;
      |                ^~~
jobs.cpp:69:18: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
   69 |     for(int i=0;i<m;++i)
      |                 ~^~

Subtask #1
55.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 18 ms 3528 KB Output isn't correct
2 Incorrect 19 ms 3528 KB Output isn't correct
3 Incorrect 20 ms 3528 KB Output isn't correct
4 Incorrect 19 ms 3528 KB Output isn't correct
5 Incorrect 21 ms 3464 KB Output isn't correct
6 Incorrect 20 ms 3652 KB Output isn't correct
7 Incorrect 21 ms 3528 KB Output isn't correct
8 Incorrect 21 ms 3448 KB Output isn't correct
9 Correct 22 ms 3528 KB Output is correct
10 Correct 25 ms 3572 KB Output is correct
11 Correct 24 ms 3520 KB Output is correct
12 Correct 60 ms 6596 KB Output is correct
13 Correct 77 ms 12692 KB Output is correct
14 Correct 107 ms 12772 KB Output is correct
15 Incorrect 123 ms 15512 KB Output isn't correct
16 Correct 167 ms 25012 KB Output is correct
17 Correct 201 ms 24964 KB Output is correct
18 Correct 205 ms 25028 KB Output is correct
19 Correct 230 ms 28032 KB Output is correct
20 Correct 212 ms 25004 KB Output is correct