Submission #388652

#	Time	Username	Problem	Language	Result	Execution time	Memory
388652		dextermorgan029	Job Scheduling (CEOI12_jobs)	C++14	0 / 100	691 ms	14684 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
#define int         long long

typedef vector<int> vi;
typedef pair<int,int> pii;
#define For(i,n)    for(int i = 0; i < (int) n; ++i)
#define rep(i,a,b)  for(int i=a;i<b;i++)

#define ll          long long
#define sz(x)       (int)((x).size())
#define lld         double
#define fr          first
#define sc          second
#define pb          push_back
#define endl        "\n"
#define ar          array
#define INF         1e18;
#define all(v)      (v).begin(),(v).end()
#define mem1(a)     memset(a,-1,sizeof(a))
#define mem0(a)     memset(a,0,sizeof(a))
#define ppc         __builtin_popcount
#define ppcll       __builtin_popcountll
const int N=2e3+12;
const int M=1e9+7;
const int M2=998244353;
void input(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
#ifndef ONLINE_JUDGE
	freopen("sabotage.in","r",stdin );
	freopen("sabotage.out","w",stdout);
#endif
}
int n,d,m,a[N];
bool go(int mid){
    map<int,vi> mp;
    vi b(n+1,mid);
    For(i,m){
        mp[a[i]].pb(i+1);

    }
    int j=n,cnt=0;
    for(int i=n;i>0;){
        cnt++;
        for(;j>0 && mp[i].size() && b[j];){
                mp[i].pop_back();
                b[j]--;
        }
        if(b[j]){
            i--;
            if(j-i==d){
                j--;
            }
        }
        else{
            if(mp[i].size()){
                if(j<i || (j-i)>d){
                    return 0;
                }
                else{
                    --j;
                }
            }
            else{
                if(j<i || (j-i)>d){
                    return 0;
                }
                --i;
                j--;
            }
        }
    }
    return 1;

}


void solve(){

    cin>>n>>d>>m;

    For(i,m){
        cin>>a[i];
    }
    //sort(all(a));
    int l=1,r=1e9;
    while(l<r){
        int mid=(l+r)/2;
        if(go(mid)){
            r=mid;
        }
        else{
            l=mid+1;
        }
    }
    cout<<l<<endl;
    map<int,vi> mp;
    vi b(n+1,l);
    For(i,m){
        mp[a[i]].pb(i+1);

    }
    int j=n,cnt=0;
    vector<vi> ans1;
    vi ans;
    for(int i=n;i>0;){
        cnt++;
        for(;j>0 && mp[i].size() && b[j];){
                ans.pb(mp[i].back());
                mp[i].pop_back();
                b[j]--;
        }
        if(b[j]){
            i--;
            if(j-i==d){
                j--;
                ans.pb(0);
                ans1.pb(ans);
                ans.clear();
            }
        }
        else{
            if(mp[i].size()){
                if(j<i || (j-i)>d){
                    return ;
                }
                else{
                    --j;
                    ans.pb(0);
                    ans1.pb(ans);
                    ans.clear();
                }
            }
            else{
                if(j<i || (j-i)>d){
                    return ;
                }
                --i;
                j--;
                ans.pb(0);
                ans1.pb(ans);
                ans.clear();
            }
        }
    }
    while(j){
        ans.pb(0);
        ans1.pb(ans);
        ans.clear();
        j--;
    }
    reverse(all(ans1));
    for(auto i:ans1){
        for(auto j:i)cout<<j<<" ";
        cout<<endl;
    }



}
signed main(){
    //input();
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    #ifdef NCR
		init();
	#endif

    int t=1;


    //cin>>t;

    int a=1;
    while(t--){
        //cout<<"Case #"<<a<<": ";
        solve();
        a+=1;
    }
}

Compilation message (stderr)

jobs.cpp: In function 'void input()':
jobs.cpp:31:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   31 |  freopen("sabotage.in","r",stdin );
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:32:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   32 |  freopen("sabotage.out","w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100