Submission #78359

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
78359	2018-10-04T05:36:27 Z	SamAnd	Job Scheduling (CEOI12_jobs)	C++17	70 / 100	280 ms	33792 KB

jobs

#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;
        }
        if(o>n)
            return false;
        if(a[i].x+d<o)
            return false;
        ++xx;
        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);
    cout<<ans<<endl;
    for(int i=1;i<=n;++i)
    {
        for(int j=0;j<v[i].size();++j)
            cout<<v[i][j]<<' ';
        cout<<0<<endl;
    }
    return 0;
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:97:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<v[i].size();++j)
                     ~^~~~~~~~~~~~
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);
         ~~~~~^~~~~~~~~~~~~~

Subtask #1

70.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	64 ms	25716 KB	Output is correct
2	Correct	74 ms	25728 KB	Output is correct
3	Correct	65 ms	25744 KB	Output is correct
4	Correct	101 ms	25748 KB	Output is correct
5	Correct	66 ms	25876 KB	Output is correct
6	Correct	68 ms	25972 KB	Output is correct
7	Correct	66 ms	25972 KB	Output is correct
8	Correct	68 ms	25972 KB	Output is correct
9	Correct	222 ms	26256 KB	Output is correct
10	Correct	225 ms	26280 KB	Output is correct
11	Correct	68 ms	26280 KB	Output is correct
12	Correct	97 ms	27948 KB	Output is correct
13	Correct	138 ms	30380 KB	Output is correct
14	Correct	213 ms	32536 KB	Output is correct
15	Runtime error	230 ms	33324 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
16	Runtime error	280 ms	33792 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
17	Runtime error	257 ms	33792 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
18	Runtime error	264 ms	33792 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
19	Runtime error	278 ms	33792 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
20	Runtime error	251 ms	33792 KB	Execution killed with signal 9 (could be triggered by violating memory limits)