Submission #78361

# Submission time Handle Problem Language Result Execution time Memory
78361 2018-10-04T05:50:00 Z SamAnd Job Scheduling (CEOI12_jobs) C++17
0 / 100
304 ms 33792 KB
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
const int N=1000006;
struct ban
{
    int x,i;
};
bool operator<(const ban& a,const ban& b)
{
    if(a.x<b.x)
        return true;
    if(a.x>b.x)
        return false;
    return a.i<b.i;
}

int n,d,m;
ban a[N];

vector<int> v[N];
void stgg(int x)
{
    int o=1,xx=0;
    for(int i=0;i<m;++i)
    {
        while(a[i].x>o)
        {
            ++o;
            xx=0;
        }
        ++xx;
        v[o].push_back(a[i].i);
        if(xx==x)
        {
            ++o;
            xx=0;
        }
    }
}

bool stg(int x)
{
    int o=1,xx=0;
    for(int i=0;i<m;++i)
    {
        while(a[i].x>o)
        {
            ++o;
            xx=0;
        }
        ++xx;
        if(o>n)
            return false;
        if(a[i].x+d<o)
            return false;
        if(xx==x)
        {
            ++o;
            xx=0;
        }
    }
    return true;
}

int byn()
{
    int l=1,r=m;
    while((r-l)>3)
    {
        int mid=(l+r)/2;
        if(stg(mid))
            r=mid;
        else
            l=mid;
    }
    for(int mid=l;mid<=r;++mid)
        if(stg(mid))
            return mid;
}

int main()
{
    //freopen("input.txt","r",stdin);
    scanf("%d%d%d",&n,&d,&m);
    for(int i=0;i<m;++i)
    {
        scanf("%d",&a[i].x);
        a[i].i=i+1;
    }
    sort(a,a+m);
    int ans=byn();
    stgg(ans);
    printf("%d\n",ans);
    /*for(int i=1;i<=n;++i)
    {
        for(int j=0;j<v[i].size();++j)
            printf("%d ",v[i][j]);
        printf("0\n");
    }*/
    return 0;
}

Compilation message

jobs.cpp: In function 'int byn()':
jobs.cpp:80:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
jobs.cpp: In function 'int main()':
jobs.cpp:85:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d",&n,&d,&m);
     ~~~~~^~~~~~~~~~~~~~~~~~~
jobs.cpp:88:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&a[i].x);
         ~~~~~^~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 25204 KB Unexpected end of file - int32 expected
2 Incorrect 47 ms 25204 KB Unexpected end of file - int32 expected
3 Incorrect 41 ms 25276 KB Unexpected end of file - int32 expected
4 Incorrect 40 ms 25312 KB Unexpected end of file - int32 expected
5 Incorrect 40 ms 25312 KB Unexpected end of file - int32 expected
6 Incorrect 42 ms 25312 KB Unexpected end of file - int32 expected
7 Incorrect 39 ms 25312 KB Unexpected end of file - int32 expected
8 Incorrect 44 ms 25328 KB Unexpected end of file - int32 expected
9 Incorrect 50 ms 25332 KB Unexpected end of file - int32 expected
10 Incorrect 48 ms 25332 KB Unexpected end of file - int32 expected
11 Incorrect 52 ms 25332 KB Unexpected end of file - int32 expected
12 Incorrect 82 ms 26600 KB Unexpected end of file - int32 expected
13 Incorrect 115 ms 28292 KB Unexpected end of file - int32 expected
14 Incorrect 152 ms 29860 KB Unexpected end of file - int32 expected
15 Incorrect 172 ms 29996 KB Unexpected end of file - int32 expected
16 Incorrect 208 ms 31404 KB Unexpected end of file - int32 expected
17 Runtime error 261 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 263 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Runtime error 304 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Runtime error 244 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)