Submission #885077

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
885077	2023-12-09T01:11:32 Z	cpptowin	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	107 ms	17236 KB

jobs

#include<bits/stdc++.h>
#define fo(i,d,c) for(int i=d;i<=c;i++)
#define fod(i,c,d) for(int i=c;i>=d;i--)
#define maxn 100010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout<<"\n";
//#define int long long
#define inf (int)1e18
#define pii pair<int,int>
#define vii vector<pii>
#define lb(x) x&-x
#define bit(i,j) ((i>>j)&1)
#define offbit(i,j) (i^(1<<j))
#define onbit(i,j) (i|(1<<j))
#define vi vector<int>
template <typename T1, typename T2> bool minimize(T1 &a, T2 b){if (a > b) {a = b; return true;} return false;}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b){if (a < b) {a = b; return true;} return false;}
using namespace std;
int cnt[maxn];
int n,d,m;
int sum[maxn];
vi ke[maxn];
int x,del,now;
bool check(int val)
{
    fo(i,1,n) cnt[i] = sum[i];
    now = 1;
    fo(i,1,n)
    {
        if(now < i - d) return 0;
        x = val;
        while(x > 0)
        {
            del = min(cnt[now],x);
            x -= del;
            cnt[now] -= del;
            if(cnt[now] == 0)
            {
                if(now < i) now++;
                else break;
            }
        }
    }
    return 1;
}
main()
{
    #define name "TASK"
    if(fopen(name".inp","r"))
    {
       freopen(name".inp","r",stdin);
       freopen(name".out","w",stdout);
    }
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    cin >> n >> d >> m;
    fo(i,1,m)
    {
        cin >> x;
        sum[x]++;
        ke[x].pb(i);
    }
    int l = 1,r = m,ans,mid;
    while(l <= r)
    {
        mid = (l + r) >> 1;
        if(check(mid)) ans = mid,r = mid - 1;
        else l = mid + 1;
    }
    cout << ans;en;
    int pos = 0,now = 1;
    fo(i,1,n)
    {
        x = ans;
        while(x > 0)
        {
            del = min(sum[now],x);
            x -= del;
            sum[now] -= del;
            for(int k = pos ; k < pos + del ; k++) cout << ke[now][k] << ' ';
            pos += del;
            if(sum[now] == 0)
            {
                if(now < i) now++,pos = 0;
                else break;
            }
        }
        cout << 0 << "\n";
    }
}

Compilation message

jobs.cpp:49:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   49 | main()
      | ^~~~
jobs.cpp: In function 'int main()':
jobs.cpp:54:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |        freopen(name".inp","r",stdin);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:55:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |        freopen(name".out","w",stdout);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:72:13: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   72 |     cout << ans;en;
      |             ^~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	4232 KB	Output is correct
2	Correct	11 ms	4316 KB	Output is correct
3	Correct	11 ms	4136 KB	Output is correct
4	Correct	12 ms	4316 KB	Output is correct
5	Correct	12 ms	4316 KB	Output is correct
6	Correct	12 ms	4312 KB	Output is correct
7	Correct	11 ms	4312 KB	Output is correct
8	Correct	11 ms	4256 KB	Output is correct
9	Correct	19 ms	5212 KB	Output is correct
10	Correct	19 ms	5212 KB	Output is correct
11	Correct	12 ms	4188 KB	Output is correct
12	Correct	26 ms	5712 KB	Output is correct
13	Correct	34 ms	8020 KB	Output is correct
14	Correct	55 ms	9812 KB	Output is correct
15	Correct	58 ms	10836 KB	Output is correct
16	Correct	80 ms	13388 KB	Output is correct
17	Correct	96 ms	15628 KB	Output is correct
18	Correct	89 ms	15444 KB	Output is correct
19	Correct	107 ms	17236 KB	Output is correct
20	Correct	93 ms	15744 KB	Output is correct