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
#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);
         ~~~~~^~~~~~~~~~~~~~
# 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)