oj.uz

Submission #1085566

# Submission time Handle Problem Language Result Execution time Memory
1085566 2024-09-08T12:28:04 Z LeonidCuk Job Scheduling (CEOI12_jobs) C++17
60 / 100
 288 ms 17096 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 28 ms 4052 KB Output isn't correct
2 Incorrect 26 ms 4100 KB Output isn't correct
3 Incorrect 26 ms 4052 KB Output isn't correct
4 Incorrect 27 ms 4196 KB Output isn't correct
5 Incorrect 27 ms 4052 KB Output isn't correct
6 Incorrect 30 ms 4048 KB Output isn't correct
7 Incorrect 28 ms 4052 KB Output isn't correct
8 Incorrect 38 ms 4004 KB Output isn't correct
9 Correct 115 ms 4456 KB Output is correct
10 Correct 119 ms 4436 KB Output is correct
11 Correct 21 ms 4184 KB Output is correct
12 Correct 38 ms 5716 KB Output is correct
13 Correct 58 ms 8020 KB Output is correct
14 Correct 101 ms 9808 KB Output is correct
15 Correct 116 ms 10940 KB Output is correct
16 Correct 149 ms 13652 KB Output is correct
17 Correct 182 ms 15892 KB Output is correct
18 Correct 159 ms 15700 KB Output is correct
19 Correct 288 ms 17096 KB Output is correct
20 Correct 193 ms 15952 KB Output is correct