oj.uz

답안 #78360

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
78360 2018-10-04T05:41:23 Z SamAnd Job Scheduling (CEOI12_jobs) C++17
70 / 100
 312 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 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

# 결과 실행 시간 메모리 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)