oj.uz

답안 #744483

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

#define ll unsigned long long
const int N = 1e6+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:14:33: warning: statement has no effect [-Wunused-value]
   14 |         if(give != x.give) give < x.give;
      |                            ~~~~~^~~~~~~~
jobs.cpp: In function 'int main()':
jobs.cpp:25:18: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
   25 |     for(int i=1;i<=m;++i)
      |                 ~^~~
jobs.cpp:29:30: warning: narrowing conversion of 'i' from 'int' to 'long long unsigned int' [-Wnarrowing]
   29 |         vec.push_back({x+d,x,i});
      |                              ^
jobs.cpp:44:22: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
   44 |         for(int i=0;i<m;++i)
      |                     ~^~
jobs.cpp:46:16: warning: unused variable 'num' [-Wunused-variable]
   46 |             ll num = day;
      |                ^~~
jobs.cpp:70:18: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
   70 |     for(int i=0;i<m;++i)
      |                 ~^~

Subtask #1
55.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 21 ms 3784 KB Output isn't correct
2 Incorrect 18 ms 3780 KB Output isn't correct
3 Incorrect 21 ms 3784 KB Output isn't correct
4 Incorrect 23 ms 3784 KB Output isn't correct
5 Incorrect 21 ms 3780 KB Output isn't correct
6 Incorrect 20 ms 3776 KB Output isn't correct
7 Incorrect 21 ms 3784 KB Output isn't correct
8 Incorrect 25 ms 3764 KB Output isn't correct
9 Correct 25 ms 3772 KB Output is correct
10 Correct 25 ms 3816 KB Output is correct
11 Correct 25 ms 3912 KB Output is correct
12 Correct 60 ms 7100 KB Output is correct
13 Correct 82 ms 13060 KB Output is correct
14 Correct 114 ms 13240 KB Output is correct
15 Incorrect 127 ms 16136 KB Output isn't correct
16 Correct 166 ms 25520 KB Output is correct
17 Correct 187 ms 25556 KB Output is correct
18 Correct 256 ms 25384 KB Output is correct
19 Correct 246 ms 28360 KB Output is correct
20 Correct 185 ms 25484 KB Output is correct