oj.uz

Submission #582439

# Submission time Handle Problem Language Result Execution time Memory
582439 2022-06-23T18:41:46 Z Dakto Let's Win the Election (JOI22_ho_t3) C++17
10 / 100
 436 ms 368 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#include <ext/pb_ds/detail/standard_policies.hpp>

using namespace std;
using namespace __gnu_pbds;

#define DEBUGMODE 1
#ifdef ONLINE_JUDGE
#define DEBUGMODE 0
#endif

#define cerr if(DEBUGMODE) cerr
#define DEBUG(a) if(DEBUGMODE) cout<<(a)<<endl
#define REP(i,n) for(int i=0; i<(n); i++)
#define REPR(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define EACH(i,c) for(auto (i):c)
#define endl '\n'
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define LLM LONG_LONG_MAX
#define gcd __gcd
#define pb push_back
#define MANY_TESTS ll ntests; cin>>ntests; for(ll test=1; test<=ntests; test++) 
#define contains(a,b) ((a).find(b)!=(a).end())
#define INF 1e16
#define NINF -1e16
#define cinv(n,v) ll n; cin>>n; vl v(n); cin>>v;
#define fact(f,n) vl f={0}; for(ll i=0; i<n; i++) f.push_back(f[i]*(i+1));
#define codejamout(s) cout<<"Case #"<<test<<": "<<s<<"\n";
#define LOG(x) cerr<<"Line "<<__LINE__<<":"<<#x<<" = "<<x<<endl;


typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pair<ll,ll>> vpll;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const ll MOD=1e9+7;

template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "(" << par.first << ";" << par.second << ")"; return out;}
template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template<class T>
ostream& operator<<(ostream& out, const vector<T> &v){ out << "[";  REP(i, v.size()) out << v[i] << ", ";  out << "]"; return out;}
// istreams
template<class T>
istream& operator>>(istream& in, vector<T> &v){ for(auto &x : v) in >> x; return in; }
template<class T, class U>
istream& operator>>(istream& in, pair<T, U> &p){ in >> p.ff >> p.ss; return in; }

template<typename T>
pair<T, ll> get_min(vector<T> &v){ typename vector<T> :: iterator it = min_element(v.begin(), v.end()); return {*it, it - v.begin()};}
template<typename T>
pair<T, ll> get_max(vector<T> &v){ typename vector<T> :: iterator it = max_element(v.begin(), v.end()); return {*it, it - v.begin()};}        
template<class T>
bool remin(T& a, const T& b){return (b<a?a=b,1:0);}
template<class T>
bool remax(T& a, const T& b){return (a<b?a=b,1:0);}

int main(){
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);

    ll n,k;
    cin>>n>>k;

    vpll v(n);

    REP(i,n){
        cin>>v[i].ff>>v[i].ss;
    }

    vpll speak, win;

    REP(i,n){
        win.pb({v[i].ff,i});
        if(v[i].ss!=-1) speak.pb({v[i].ss, i});
    }

    sort(all(win));
    sort(all(speak));

    ll s=speak.size();

    auto check=[&](double x){
        for(ll cnt=0; cnt<=s; cnt++){
            double t=x, sm=0;
            set<ll> used;
            REP(i, cnt){
                used.insert(speak[i].ss);
                sm+=(double)speak[i].ff/(1+i);
                t-=speak[i].ff;
                t+=x-sm;
            }

            ll left=k-cnt;
            ll p=0;
            while(left>0){
                if(used.count(win[p].ss)==0){
                    left--;
                    t-=win[p].ff;
                }
                p++;
            }
            if(t>=0) return true;
        }
        return false;
    };

    double l=0, r=1e6;

    while(r-l>1e-6){
        double mid=(l+r)/2;
        if(check(mid)){
            r=mid;
        }
        else{
            l=mid;
        }
    }

    cout<<r<<endl;
    
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 129 ms 352 KB Output is correct
13 Correct 64 ms 340 KB Output is correct
14 Correct 10 ms 344 KB Output is correct
15 Correct 286 ms 356 KB Output is correct
16 Correct 133 ms 348 KB Output is correct
17 Correct 29 ms 340 KB Output is correct
18 Correct 436 ms 368 KB Output is correct
19 Correct 217 ms 348 KB Output is correct
20 Correct 41 ms 316 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Incorrect 1 ms 212 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Incorrect 1 ms 212 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Incorrect 1 ms 212 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 311 ms 352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 129 ms 352 KB Output is correct
13 Correct 64 ms 340 KB Output is correct
14 Correct 10 ms 344 KB Output is correct
15 Correct 286 ms 356 KB Output is correct
16 Correct 133 ms 348 KB Output is correct
17 Correct 29 ms 340 KB Output is correct
18 Correct 436 ms 368 KB Output is correct
19 Correct 217 ms 348 KB Output is correct
20 Correct 41 ms 316 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 1 ms 212 KB Output is correct
28 Correct 1 ms 320 KB Output is correct
29 Incorrect 1 ms 212 KB Output isn't correct
30 Halted 0 ms 0 KB -