/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 320.0 KiB
#2 Accepted 57ms 532.0 KiB
#3 Accepted 86ms 1.297 MiB
#4 Accepted 79ms 1.301 MiB
#5 Accepted 88ms 1.293 MiB
#6 Accepted 80ms 1.27 MiB
#7 Accepted 79ms 1.062 MiB
#8 Accepted 82ms 1.289 MiB
#9 Accepted 78ms 1.301 MiB
#10 Accepted 83ms 1.293 MiB
#11 Accepted 90ms 1.289 MiB
#12 Accepted 82ms 1.062 MiB
#13 Accepted 83ms 1.27 MiB
#14 Accepted 80ms 1.27 MiB
#15 Accepted 81ms 1.27 MiB
#16 Accepted 93ms 1.285 MiB
#17 Accepted 81ms 1.289 MiB
#18 Accepted 82ms 1.27 MiB
#19 Accepted 80ms 1.27 MiB
#20 Accepted 80ms 1.086 MiB

Code

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
bool pos(ll mid, ll sum){
    ll need = (mid * (mid+1))/2;
    return sum >= need;
}
void solve()
{
    ll n;
    cin >> n;
    vector<ll> v(n);
    ll tot = 0;
    for(auto &x:v){
        cin>>x;
        tot += x;
    }
    ll l = 0, r = 1e9;
    while(l < r){
        ll mid = (l + r + 1)/2;
        if(pos(mid, tot)){
            l = mid;
        }
        else{
            r = mid - 1;
        }
    }
    cout<<l+1<<endl;
}
int main()
{
    int tc = 1, cs = 1;
    cin >> tc;
    while (tc--)
    {
        // cout<<"Case "<<cs<<": ";
        solve();
    }
    return 0;
}

Information

Submit By
Type
Submission
Problem
P1114 Maximize the MEX
Contest
Brain Booster #7
Language
C++17 (G++ 13.2.0)
Submit At
2024-11-05 16:25:20
Judged At
2024-11-05 16:25:20
Judged By
Score
100
Total Time
93ms
Peak Memory
1.301 MiB