oj.uz

답안 #744016

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
744016 2023-05-18T07:12:52 Z riodsa Job Scheduling (CEOI12_jobs) C++17
55 / 100
 287 ms 28192 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 21 ms 3656 KB Output isn't correct
2 Incorrect 24 ms 3656 KB Output isn't correct
3 Incorrect 22 ms 3708 KB Output isn't correct
4 Incorrect 21 ms 3656 KB Output isn't correct
5 Incorrect 20 ms 3648 KB Output isn't correct
6 Incorrect 21 ms 3644 KB Output isn't correct
7 Incorrect 25 ms 3656 KB Output isn't correct
8 Incorrect 25 ms 3656 KB Output isn't correct
9 Correct 25 ms 3680 KB Output is correct
10 Correct 32 ms 3660 KB Output is correct
11 Correct 28 ms 3784 KB Output is correct
12 Correct 59 ms 6884 KB Output is correct
13 Correct 92 ms 12940 KB Output is correct
14 Correct 128 ms 12968 KB Output is correct
15 Incorrect 151 ms 15804 KB Output isn't correct
16 Correct 187 ms 25308 KB Output is correct
17 Correct 226 ms 25336 KB Output is correct
18 Correct 240 ms 25236 KB Output is correct
19 Correct 287 ms 28192 KB Output is correct
20 Correct 244 ms 25272 KB Output is correct