Submission #885077

#	Time	Username	Problem	Language	Result	Execution time	Memory
885077		cpptowin	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	107 ms	17236 KiB

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 (stderr)

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 / 100