Submission #854390

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
854390	2023-09-27T09:07:24 Z	nnhzzz	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	202 ms	13892 KB

jobs

// cre: Nguyen Ngoc Hung - Train VOI 2024

#include<bits/stdc++.h>

using namespace std;

#define        __nnhzzz__  signed main()
#define          BIT(i,j)  ((i>>j)&1LL)
#define           MASK(i)  (1LL<<i)
#define            ALL(x)  (x).begin(),(x).end()
#define             SZ(x)  (int)(x).size()
#define                fi  first
#define                se  second
#define                ll  long long
#define               ull  unsigned long long
#define                ld  long double
#define                vi  vector<int>
#define               vvi  vector<vi>
#define              vvvi  vector<vvi>
#define               pii  pair<int,int>
#define              vpii  vector<pii>
#define        REP(i,a,b)  for(int i = (a); i<=(b); ++i)
#define       REPD(i,a,b)  for(int i = (a); i>=(b); --i)
#define   REPDIS(i,a,b,c)  for(int i = (a); i<=(b); i+=c)

//-------------------------------------------------------------//
const int oo = 1e9,LOG = 20,MAXN = 1e6+7,N = 1e2+3;
const int MOD = 1e9+7,MOD1 = 1e9+207,MOD2 = 1e9+407,MOD3 = 998244353;
//-------------------------------------------------------------//
template<typename T1, typename T2> bool mini(T1 &a, T2 b){if(a>b){a=b;return true;}return false;}
template<typename T1, typename T2> bool maxi(T1 &a, T2 b){if(a<b){a=b;return true;}return false;}

/*
----------------------------------------------------------------
    END OF TEMPLATE
----------------------------------------------------------------
    Nguyen Ngoc Hung - nnhzzz
    Training for VOI24 gold medal
----------------------------------------------------------------
*/

pii a[MAXN];
int n,k,m;

bool ok(int x){
    int pos = 1;
    REP(i,1,n){
        for(int j = 1; j<=x && pos<=m && a[pos].fi<=i; ++j){
            if(i-a[pos].fi>k){
                return false;
            }
            ++pos;
        }
    }
    return pos==m+1;
}

void solve(){
    cin >> n >> k >> m;
    REP(i,1,m){
        cin >> a[i].fi;
        a[i].se = i;
    }
    sort(a+1,a+m+1);
    int l = 1,r = m+1,res = m+1;
    while(l<=r){
        int mid = (l+r)>>1;
        if(ok(mid)==true){
            res = mid;
            r = mid-1;
        }else{
            l = mid+1;
        }
    }
    cout << res << "\n";
    int pos = 1;
    REP(i,1,n){
        for(int j = 1; j<=res && pos<=m && a[pos].fi<=i; ++j,++pos){
            cout << a[pos].se << " ";
        }
        cout << "0\n";
    }
}

__nnhzzz__{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #define name "test"
    if(fopen(name".inp","r")){
        freopen(name".inp","r",stdin);
        freopen(name".out","w",stdout);
    }
    #define name1 "nnhzzz"
    if(fopen(name1".inp","r")){
        freopen(name1".inp","r",stdin);
        freopen(name1".out","w",stdout);
    }
    int test = 1;
    while(test--){
        solve();
    }
    cerr << "\nTime elapsed: " << 1000*clock()/CLOCKS_PER_SEC << "ms\n";
    return 0;
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:90:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |         freopen(name".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:91:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         freopen(name".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:95:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |         freopen(name1".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:96:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |         freopen(name1".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	3160 KB	Output is correct
2	Correct	13 ms	3164 KB	Output is correct
3	Correct	13 ms	3160 KB	Output is correct
4	Correct	15 ms	3160 KB	Output is correct
5	Correct	13 ms	3160 KB	Output is correct
6	Correct	15 ms	3164 KB	Output is correct
7	Correct	14 ms	3416 KB	Output is correct
8	Correct	18 ms	3164 KB	Output is correct
9	Correct	22 ms	3420 KB	Output is correct
10	Correct	24 ms	3416 KB	Output is correct
11	Correct	20 ms	3160 KB	Output is correct
12	Correct	41 ms	3924 KB	Output is correct
13	Correct	63 ms	6504 KB	Output is correct
14	Correct	85 ms	7280 KB	Output is correct
15	Correct	103 ms	8060 KB	Output is correct
16	Correct	128 ms	10856 KB	Output is correct
17	Correct	151 ms	11392 KB	Output is correct
18	Correct	170 ms	12200 KB	Output is correct
19	Correct	202 ms	13892 KB	Output is correct
20	Correct	152 ms	11604 KB	Output is correct