Submission #78360

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
78360	2018-10-04T05:41:23 Z	SamAnd	Job Scheduling (CEOI12_jobs)	C++17	70 / 100	312 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;
        }
        ++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 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	54 ms	25760 KB	Output is correct
2	Correct	60 ms	25864 KB	Output is correct
3	Correct	69 ms	25948 KB	Output is correct
4	Correct	49 ms	25948 KB	Output is correct
5	Correct	52 ms	26004 KB	Output is correct
6	Correct	49 ms	26004 KB	Output is correct
7	Correct	79 ms	26004 KB	Output is correct
8	Correct	55 ms	26004 KB	Output is correct
9	Correct	73 ms	26252 KB	Output is correct
10	Correct	63 ms	26252 KB	Output is correct
11	Correct	60 ms	26252 KB	Output is correct
12	Correct	98 ms	27944 KB	Output is correct
13	Correct	135 ms	30376 KB	Output is correct
14	Correct	184 ms	32552 KB	Output is correct
15	Runtime error	219 ms	33448 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	312 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	239 ms	33792 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
18	Runtime error	262 ms	33792 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
19	Runtime error	276 ms	33792 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
20	Runtime error	232 ms	33792 KB	Execution killed with signal 9 (could be triggered by violating memory limits)