oj.uz

Submission #1003148

# Submission time Handle Problem Language Result Execution time Memory
1003148 2024-06-20T06:50:15 Z vjudge1 Rice Hub (IOI11_ricehub) C++17
0 / 100
 1000 ms 11092 KB 
#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
#define ins insert
#define pb push_back
// #define int long long int
#define pii pair<int, int>
#define endl '\n'
#define drop(x) cout<<(x)<<endl; return;
#define all(x) x.begin(),x.end()

int calc(int n,int mid,int arr[],int B){

    multiset<pair<int,int>> lst;
    for(int i=0;i<n;i++){
        lst.ins({abs(arr[i]-mid),i});
    }
    int cnt=0;
    for(auto v:lst){
        if(B-v.first<0){
            break;
        }
        ++cnt;
        B-=v.first;
    }

    return cnt;
}

int besthub(int R, int L, int arr[], long long B){
/*
    dusun:

        hemise hansisa arr[i] e qoymaq mentiqlidi,

        binary search atib, i - j arasina gore j' - i arasini calclamaq?


            i nen j olsa, i<j'<j lerin hamisini nece costa i ye getirerik?

                arr[j']-arr[i]
                0 2 
                arr[j'+1] - arr[i] = arr[j'] -  arr[i] + (arr[j'+1]-arr[j'])
                arr[j' +2] - arr[i] = arr[j'] - arr[i] + (arr[j'+1]-arr[j']) + (arr[j'+2]-arr[j'+1])

                (arr[j'+1]-arr[j']) x (j-i)
                (arr[j'+2]-arr[j'+1]) x (j-i-1) = arr[j']

                i->j  : (arr[j'] - arr[i])*(j-i) + 
                xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx


                (pref[r] - pref[l]) - ( arr[i] - arr[0] * (r-l) )
*/
    int anstot=1;
    int n = R;
    map<int,int> var;
    // vector<int> pref(R+1,0);
    // for(int i=0;i<n;i++){
    //     pref[i]=arr[i] - arr[0];
    //     if(i){
    //         pref[i]+=pref[i-1];
    //     }
    //     var[arr[i]]++;
    //     anstot= max(anstot,var[arr[i]]);
    // }
    map<int,int> comp;
    for(int i=0;i<n;i++){
        comp[arr[i]]++;
    }
    int cnt=1;
    for(auto& v:comp){
        v.second = (cnt++);
    }


    int l =1;
    int r = 1e9;
    int ans=0;
    while(l<=r){
        int mid = (l+r)/2;

        /*
            pointi mid e qoysaq, cavab nece olur
        */
        int mc =   calc(n,mid,arr,B);
        int lmc =  calc(n,mid-1,arr,B);
        int rmc =  calc(n,mid+1,arr,B);
        ans=max(ans,mc);
        // cout<<mid<<" "<<mc<<endl;
        if(lmc>=rmc){
            r=mid-1;
        }
        else{
            l=mid+1;
        }

    }   
    l = 1;
    r = 1e9;
    while(l<=r){
        int mid = (l+r)/2;

        /*
            pointi mid e qoysaq, cavab nece olur
        */
        int mc =   calc(n,mid,arr,B);
        int lmc =  calc(n,mid-1,arr,B);
        int rmc =  calc(n,mid+1,arr,B);
        ans=max(ans,mc);
        // cout<<mid<<" "<<mc<<endl;
        if(rmc>=lmc){
            r=mid-1;
        }
        else{
            l=mid+1;
        }

    }   
    // cout<<ans<<endl;
    // anstot=ans;

    return ans;
}

Compilation message

ricehub.cpp: In function 'int besthub(int, int, int*, long long int)':
ricehub.cpp:55:9: warning: unused variable 'anstot' [-Wunused-variable]
   55 |     int anstot=1;
      |         ^~~~~~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 452 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Incorrect 1 ms 348 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 6 ms 348 KB Output is correct
4 Correct 9 ms 540 KB Output is correct
5 Correct 4 ms 396 KB Output is correct
6 Correct 3 ms 344 KB Output is correct
7 Correct 8 ms 348 KB Output is correct
8 Correct 6 ms 348 KB Output is correct
9 Correct 4 ms 424 KB Output is correct
10 Correct 4 ms 348 KB Output is correct
11 Correct 8 ms 348 KB Output is correct
12 Correct 6 ms 344 KB Output is correct
13 Correct 8 ms 548 KB Output is correct
14 Incorrect 7 ms 544 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 2392 KB Output is correct
2 Correct 240 ms 2508 KB Output is correct
3 Execution timed out 1071 ms 11092 KB Time limit exceeded
4 Halted 0 ms 0 KB -