oj.uz

Submission #1085564

# Submission time Handle Problem Language Result Execution time Memory
1085564 2024-09-08T12:25:31 Z vjudge1 Job Scheduling (CEOI12_jobs) C++17
60 / 100
 283 ms 17088 KB 
#include <bits/stdc++.h>
using namespace std;
int n,m,k;
vector<int>v[100001];
bool check(int x)
{
    int t=v[1].size(),l=1;
    for(int i=1;i<=k;i++)
    {
        int temp=x;
        if(l+m<i)
        {
            return false;
        }
        while(l<=i)
        {
            if(t<=temp)
            {
                l++;
                temp-=t;
                t=v[l].size();
            }
            else
            {
                t-=temp;
                break;
            }
        }
    }
    if(l!=k+1)
    {
        return false;
    }
    return true;
}
int main()
{
    int a;
    cin>>k>>m>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a;
        v[a].push_back(i+1);
    }
    int l=1,r=k;
    while(l<r)
    {
        int mid=(l+r)/2;
        if(check(mid))
        {
            r=mid;
        }
        else
        {
            l=mid+1;
        }
    }
    cout<<r<<endl;
    l=1;
    int t=v[1].size(),lx=0;
    for(int i=1;i<=k;i++)
    {
          int temp=r;
          while(l<=i)
          {
            if(t<=temp)
            {
                for(int j=lx;j<v[l].size();j++)
                {
                    cout<<v[l][j]<<" ";
                }
                l++;
                lx=0;
                temp-=t;
                t=v[l].size();
            }
            else
            {
                for(int j=lx;j<lx+temp;j++)
                {
                    cout<<v[l][j]<<" ";
                }
                lx+=temp;
                t-=temp;
                break;
            }
          }
          cout<<"0"<<endl;
    }
    return 0;
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:68:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |                 for(int j=lx;j<v[l].size();j++)
      |                              ~^~~~~~~~~~~~

Subtask #1
60.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 4140 KB Output isn't correct
2 Incorrect 28 ms 4048 KB Output isn't correct
3 Incorrect 28 ms 4052 KB Output isn't correct
4 Incorrect 27 ms 4052 KB Output isn't correct
5 Incorrect 26 ms 4048 KB Output isn't correct
6 Incorrect 27 ms 4192 KB Output isn't correct
7 Incorrect 27 ms 4048 KB Output isn't correct
8 Incorrect 27 ms 4052 KB Output isn't correct
9 Correct 124 ms 4432 KB Output is correct
10 Correct 118 ms 4436 KB Output is correct
11 Correct 41 ms 4180 KB Output is correct
12 Correct 50 ms 5840 KB Output is correct
13 Correct 64 ms 8020 KB Output is correct
14 Correct 128 ms 10028 KB Output is correct
15 Correct 133 ms 11132 KB Output is correct
16 Correct 164 ms 13604 KB Output is correct
17 Correct 179 ms 16000 KB Output is correct
18 Correct 156 ms 15732 KB Output is correct
19 Correct 283 ms 17088 KB Output is correct
20 Correct 189 ms 15956 KB Output is correct