oj.uz

답안 #684979

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
684979 2023-01-23T03:44:28 Z nikhil_kumart21 Job Scheduling (CEOI12_jobs) C++17
100 / 100
 164 ms 29624 KB 

#include <bits/stdc++.h>

using namespace std;

typedef int ll;
#define endl "\n";

void setIO(string s) {
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}
vector<vector<ll>>v;
vector<ll>row;
vector<vector<ll>>A,M;
ll fun(ll a[],ll n,ll mid,ll d,ll done){
    deque<ll>dq;
    v.clear();
    for(ll i=1;i<=n;++i){
        if(dq.size()>d)return 0;
        ll x=mid;
        row.clear();
        dq.push_back(a[i]);
        while(!dq.empty()){
            if(dq.front()<=x){
                x-=dq.front();
                if(dq.front()!=0&&done){
                    for(ll j=0;j<dq.front();++j){
                        row.push_back(i-dq.size()+1);
                    }
                }
                dq.pop_front();
            }
            else{
                dq.front()-=x;
                if(x!=0&&done){
                    for(ll j=0;j<x;++j){
                        row.push_back(i-dq.size()+1);
                    }
                }
                break;
            }
        }
        if(!row.empty()&&done)v.push_back(row);
    }
    return dq.size()<=d;
}
int main()
{
    // setIO("angry");
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    ll n,d,m;
    cin>>n>>d>>m;
    ll a[n+1];
    memset(a,0,sizeof(a));
    M=vector<vector<ll>>(n+1);
    for(ll i=0;i<m;++i){
        ll x;
        cin>>x;
        M[x].push_back(i+1);
        a[x]++;
    }
    ll l=1,r=m,mid,ans=1e15;
    while(l<=r){
        mid=l+(r-l)/2;
        if(fun(a,n,mid,d,0)){
            ans=mid;
            r=mid-1;
        }
        else{
            l=mid+1;
        }
    }
    fun(a,n,ans,d,1);
    A=v;
    for(ll i=0;i<A.size();++i){
        for(ll j=0;j<A[i].size();++j){
            ll x=A[i][j];
            A[i][j]=M[x].back();
            M[x].pop_back();
        }
        A[i].push_back(0);
    }
    while(A.size()<n){
        A.push_back({0});
    }
    cout<<ans<<endl;
    for(ll i=0;i<n;++i){
        auto it=A[i];
        for(auto it2:it){
            cout<<it2;
            if(it2!=0)
            cout<<" ";
        }
        if(i!=n-1)
        cout<<endl;
    }
    // for(auto it:M){
    //     for(auto it2:it){
    //         cout<<it2<<" ";
    //     }
    //     cout<<endl;
    // }
}

Compilation message

jobs.cpp: In function 'll fun(ll*, ll, ll, ll, ll)':
jobs.cpp:21:21: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
   21 |         if(dq.size()>d)return 0;
      |            ~~~~~~~~~^~
jobs.cpp:47:21: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
   47 |     return dq.size()<=d;
      |            ~~~~~~~~~^~~
jobs.cpp: In function 'int main()':
jobs.cpp:65:24: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '1.0e+15' to '2147483647' [-Woverflow]
   65 |     ll l=1,r=m,mid,ans=1e15;
      |                        ^~~~
jobs.cpp:78:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for(ll i=0;i<A.size();++i){
      |                ~^~~~~~~~~
jobs.cpp:79:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         for(ll j=0;j<A[i].size();++j){
      |                    ~^~~~~~~~~~~~
jobs.cpp:86:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
   86 |     while(A.size()<n){
      |           ~~~~~~~~^~
jobs.cpp: In function 'void setIO(std::string)':
jobs.cpp:11:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |  freopen((s + ".in").c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:12:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |  freopen((s + ".out").c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 3404 KB Output is correct
2 Correct 16 ms 3468 KB Output is correct
3 Correct 17 ms 3404 KB Output is correct
4 Correct 16 ms 3372 KB Output is correct
5 Correct 16 ms 3404 KB Output is correct
6 Correct 16 ms 3432 KB Output is correct
7 Correct 16 ms 3420 KB Output is correct
8 Correct 18 ms 3376 KB Output is correct
9 Correct 45 ms 11412 KB Output is correct
10 Correct 36 ms 11656 KB Output is correct
11 Correct 16 ms 2708 KB Output is correct
12 Correct 34 ms 5036 KB Output is correct
13 Correct 50 ms 8120 KB Output is correct
14 Correct 76 ms 11368 KB Output is correct
15 Correct 79 ms 12448 KB Output is correct
16 Correct 115 ms 15976 KB Output is correct
17 Correct 128 ms 19240 KB Output is correct
18 Correct 123 ms 20300 KB Output is correct
19 Correct 164 ms 29624 KB Output is correct
20 Correct 129 ms 19156 KB Output is correct