oj.uz

Submission #388652

# Submission time Handle Problem Language Result Execution time Memory
388652 2021-04-12T13:14:30 Z dextermorgan029 Job Scheduling (CEOI12_jobs) C++14
0 / 100
 691 ms 14684 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 1700 KB Output isn't correct
2 Incorrect 48 ms 1716 KB Output isn't correct
3 Incorrect 49 ms 1720 KB Output isn't correct
4 Incorrect 49 ms 1716 KB Output isn't correct
5 Incorrect 48 ms 1732 KB Output isn't correct
6 Incorrect 56 ms 1720 KB Output isn't correct
7 Incorrect 56 ms 1700 KB Output isn't correct
8 Incorrect 47 ms 1736 KB Output isn't correct
9 Incorrect 687 ms 14656 KB Output isn't correct
10 Incorrect 691 ms 14640 KB Output isn't correct
11 Incorrect 12 ms 464 KB Output isn't correct
12 Incorrect 7 ms 460 KB Output isn't correct
13 Incorrect 6 ms 448 KB Output isn't correct
14 Incorrect 87 ms 1920 KB Output isn't correct
15 Incorrect 12 ms 460 KB Output isn't correct
16 Runtime error 79 ms 2968 KB Execution killed with signal 11
17 Runtime error 1 ms 460 KB Execution killed with signal 11
18 Incorrect 68 ms 1844 KB Output isn't correct
19 Incorrect 691 ms 14684 KB Output isn't correct
20 Runtime error 1 ms 460 KB Execution killed with signal 11