Submission #78358

# Submission time Handle Problem Language Result Execution time Memory
78358 2018-10-04T05:35:32 Z SamAnd Job Scheduling (CEOI12_jobs) C++17
0 / 100
28 ms 24200 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];
bool stgg(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;
        v[o].push_back(a[i].i);
        if(xx==x)
        {
            ++o;
            xx=0;
        }
    }
    return true;
}

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:102: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:85:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
jobs.cpp: In function 'int main()':
jobs.cpp:89:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("input.txt","r",stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:90: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:93: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 23 ms 23800 KB Output isn't correct
2 Incorrect 23 ms 23800 KB Output isn't correct
3 Incorrect 24 ms 23836 KB Output isn't correct
4 Incorrect 28 ms 23892 KB Output isn't correct
5 Incorrect 24 ms 23924 KB Output isn't correct
6 Incorrect 27 ms 23976 KB Output isn't correct
7 Incorrect 23 ms 23976 KB Output isn't correct
8 Incorrect 25 ms 24104 KB Output isn't correct
9 Incorrect 24 ms 24104 KB Output isn't correct
10 Incorrect 24 ms 24104 KB Output isn't correct
11 Incorrect 25 ms 24200 KB Output isn't correct
12 Incorrect 23 ms 24200 KB Output isn't correct
13 Incorrect 23 ms 24200 KB Output isn't correct
14 Incorrect 24 ms 24200 KB Output isn't correct
15 Incorrect 23 ms 24200 KB Output isn't correct
16 Incorrect 23 ms 24200 KB Output isn't correct
17 Incorrect 23 ms 24200 KB Output isn't correct
18 Incorrect 23 ms 24200 KB Output isn't correct
19 Incorrect 25 ms 24200 KB Output isn't correct
20 Incorrect 24 ms 24200 KB Output isn't correct