oj.uz

답안 #1003394

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1003394 2024-06-20T09:39:51 Z AtinaR Job Scheduling (CEOI12_jobs) C++14
95 / 100
 261 ms 34624 KB 
#include <bits/stdc++.h>

using namespace std;
const int MAX=1e6+10;
const int N=1e5+10;
pair<long long,long long> niza[MAX];
long long n,d,m;
vector<long long> ress[N];
bool work(int mid)
{
    if(mid<=0)return false;
    if(mid>=m)return true;
    int i=0;
    for(int day=1; day<=n; day++)
    {
        for(int j=0; j<mid; j++)
        {
            if(i>=m)break;
            if(niza[i].first>day)break;
            if(niza[i].first+d<day)return false;
            i++;
        }
    }
    return (i>=m);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>n>>d>>m;
    for(long long i=0; i<m; i++)
    {
        cin>>niza[i].first;
        niza[i].second=i+1;
    }
    sort(niza,niza+m);
    long long b=0,e=m;
    long long res=0;
    while(b<e)
    {
        long long mid=(b+e)/2;
        bool flag=work(mid);
        if(flag)
        {
            res=mid;
            e=mid;
        }
        else b=mid+1;
    }
    cout<<res<<endl;
    int i=0;
    for(int day=1; day<=n; day++)
    {
        for(int j=0; j<res; j++)
        {
            if(i>=m)break;
            if(niza[i].first>day)break;
            ress[day].push_back(niza[i].second);
            i++;
        }
    }
    for(i=1; i<=n; i++)
    {
        for(auto x:ress[i])cout<<x<<" ";
        cout<<0<<endl;
    }
    return 0;
}
/*

8 2 12
1 2 4 2 1 3 5 6 2 3 6 4
*/

Subtask #1
95.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 5984 KB Output is correct
2 Correct 23 ms 6208 KB Output is correct
3 Correct 26 ms 5984 KB Output is correct
4 Correct 28 ms 5980 KB Output is correct
5 Correct 23 ms 5980 KB Output is correct
6 Correct 23 ms 5984 KB Output is correct
7 Correct 21 ms 5984 KB Output is correct
8 Correct 26 ms 5984 KB Output is correct
9 Correct 123 ms 6228 KB Output is correct
10 Correct 113 ms 6312 KB Output is correct
11 Correct 18 ms 6304 KB Output is correct
12 Correct 51 ms 9968 KB Output is correct
13 Correct 60 ms 14420 KB Output is correct
14 Correct 89 ms 18768 KB Output is correct
15 Correct 94 ms 19796 KB Output is correct
16 Correct 128 ms 24148 KB Output is correct
17 Correct 144 ms 31824 KB Output is correct
18 Correct 171 ms 31824 KB Output is correct
19 Runtime error 261 ms 34624 KB Memory limit exceeded
20 Correct 143 ms 31824 KB Output is correct