Submission #442251

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
442251	2021-07-07T10:43:26 Z	cpp219	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	244 ms	9796 KB

jobs

#pragma GCC optimization O2
#pragma GCC optimization "unroll-loop"
#pragma target ("avx2")

#include <bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 1e6 + 9;
const ll Log2 = 20;
const ll inf = 1e9 + 7;

ll n,m,d,a[N],pos[N];

bool lf(ll x,ll y){
    return a[x] < a[y];
}

vector<ll> ans[100009];

bool chk(ll mid){
    ll cur = 1;
    for (ll day = 1;day <= n;day++){
        ll have = mid; ans[day].clear();
        while(have > 0 && cur <= m&&a[pos[cur]] <= day){
            if (day - a[pos[cur]] > d) return 0;
            //ans[day].push_back(pos[cur]);
            cur++; have--;
        }
    }
    return 1;
}

int main(){
    ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
    #define task "test"
    if (fopen(task".INP","r")){
        freopen(task".INP","r",stdin);
        //freopen(task".OUT","w",stdout);
    }
    cin>>n>>d>>m;
    for (ll i = 1;i <= m;i++) cin>>a[i],pos[i] = i;
    sort(pos + 1,pos + m + 1,lf);
    ll l,mid,h; l = 1; h = m;
    //cout<<chk(2); return 0;
    while(l <= h){
        mid = (l + h)/2;
        if (chk(mid)) h = mid - 1;
        else l = mid + 1;
    }
    cout<<l<<"\n"; chk(l); //return 0;
    for (ll i = 1;i <= n;i++){
        for (auto j : ans[i]) cout<<j<<" "; cout<<"0\n";
    }
}

Compilation message

jobs.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    1 | #pragma GCC optimization O2
      | 
jobs.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization "unroll-loop"
      | 
jobs.cpp:3: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    3 | #pragma target ("avx2")
      | 
jobs.cpp: In function 'int main()':
jobs.cpp:56:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   56 |         for (auto j : ans[i]) cout<<j<<" "; cout<<"0\n";
      |         ^~~
jobs.cpp:56:45: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   56 |         for (auto j : ans[i]) cout<<j<<" "; cout<<"0\n";
      |                                             ^~~~
jobs.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	3416 KB	Output is correct
2	Correct	15 ms	3464 KB	Output is correct
3	Correct	20 ms	3468 KB	Output is correct
4	Correct	19 ms	3472 KB	Output is correct
5	Correct	16 ms	3412 KB	Output is correct
6	Correct	15 ms	3404 KB	Output is correct
7	Correct	15 ms	3376 KB	Output is correct
8	Correct	16 ms	3404 KB	Output is correct
9	Correct	24 ms	3592 KB	Output is correct
10	Correct	25 ms	3596 KB	Output is correct
11	Correct	23 ms	3404 KB	Output is correct
12	Correct	52 ms	4172 KB	Output is correct
13	Correct	76 ms	5008 KB	Output is correct
14	Correct	112 ms	5716 KB	Output is correct
15	Correct	126 ms	6576 KB	Output is correct
16	Correct	174 ms	7348 KB	Output is correct
17	Correct	216 ms	8040 KB	Output is correct
18	Correct	211 ms	8856 KB	Output is correct
19	Correct	244 ms	9796 KB	Output is correct
20	Correct	223 ms	8060 KB	Output is correct