CSES - Aalto Competitive Programming 2024 - wk2 - Mon - Results
Submission details
Task:Establish equality
Sender:bubu2006
Submission time:2024-09-09 16:32:12 +0300
Language:C++ (C++20)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.00 sdetails
#3ACCEPTED0.00 sdetails
#4ACCEPTED0.00 sdetails
#5ACCEPTED0.00 sdetails
#6ACCEPTED0.00 sdetails
#7ACCEPTED0.00 sdetails
#8ACCEPTED0.00 sdetails
#9ACCEPTED0.00 sdetails
#10ACCEPTED0.00 sdetails
#11ACCEPTED0.00 sdetails
#12ACCEPTED0.00 sdetails
#13ACCEPTED0.00 sdetails
#14ACCEPTED0.00 sdetails
#15ACCEPTED0.00 sdetails
#16ACCEPTED0.00 sdetails
#17ACCEPTED0.00 sdetails
#18ACCEPTED0.00 sdetails
#19ACCEPTED0.00 sdetails
#20ACCEPTED0.00 sdetails
#21ACCEPTED0.00 sdetails
#22ACCEPTED0.00 sdetails
#23ACCEPTED0.00 sdetails
#24ACCEPTED0.00 sdetails
#25ACCEPTED0.00 sdetails
#26ACCEPTED0.00 sdetails
#27ACCEPTED0.00 sdetails
#28ACCEPTED0.00 sdetails
#29ACCEPTED0.00 sdetails
#30ACCEPTED0.00 sdetails
#31ACCEPTED0.00 sdetails
#32ACCEPTED0.00 sdetails
#33ACCEPTED0.00 sdetails
#34ACCEPTED0.00 sdetails
#35ACCEPTED0.00 sdetails
#36ACCEPTED0.00 sdetails
#37ACCEPTED0.00 sdetails
#38ACCEPTED0.00 sdetails
#39ACCEPTED0.00 sdetails
#40ACCEPTED0.00 sdetails
#41ACCEPTED0.01 sdetails
#42ACCEPTED0.01 sdetails
#43ACCEPTED0.01 sdetails
#44ACCEPTED0.01 sdetails
#45ACCEPTED0.01 sdetails
#46ACCEPTED0.02 sdetails
#47ACCEPTED0.02 sdetails
#48ACCEPTED0.02 sdetails
#49ACCEPTED0.03 sdetails
#50ACCEPTED0.03 sdetails
#51ACCEPTED0.05 sdetails
#52ACCEPTED0.05 sdetails
#53ACCEPTED0.05 sdetails
#54ACCEPTED0.05 sdetails
#55ACCEPTED0.05 sdetails

Code

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

string to_string(string s) {
    return '"' + s + '"';
}
 
string to_string(const char* s) {
    return to_string((string) s);
}
 
string to_string(bool b) {
    return (b ? "true" : "false");
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
    return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A>
string to_string(A v) {
    bool first = true;
    string res = "{";
    for (const auto &x : v) {
        if (!first) {
            res += ", ";
        }
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}
 
void debug_out() {
    cerr << endl;
}
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << to_string(H);
    debug_out(T...);
}
 
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

const int N = 2e5 + 5;

int n, a[N];

signed main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    sort(a + 1, a + n + 1);

    auto check = [&](int mid) {
        int need = 0, have = 0;
        for (int i = 1; i <= n; i++) {
            if (a[i] <= mid) {
                need += (mid - a[i]) * 2;
            } else {
                have += ((a[i] - mid) / 2) * 2;
            }
        }
        return have >= need;
    };

    int lo = 0, hi = 1e9, ans = -1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (check(mid)) {
            ans = mid;
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }

    cout << ans << '\n';
}

Test details

Test 1

Verdict: ACCEPTED

input
1

correct output
4

user output
4

Test 2

Verdict: ACCEPTED

input
2
4 2 

correct output
2

user output
2

Test 3

Verdict: ACCEPTED

input
2
6 0 

correct output
2

user output
2

Test 4

Verdict: ACCEPTED

input
3
10 9 6 

correct output
7

user output
7

Test 5

Verdict: ACCEPTED

input
6
2 0 9 9 2 4 

correct output
3

user output
3

Test 6

Verdict: ACCEPTED

input
10
4 10 7 10 0 1 3 10 1 2 

correct output
3

user output
3

Test 7

Verdict: ACCEPTED

input
10
4 2 0 10 6 10 4 5 4 3 

correct output
4

user output
4

Test 8

Verdict: ACCEPTED

input
10
6 0 7 9 3 1 5 6 9 4 

correct output
3

user output
3

Test 9

Verdict: ACCEPTED

input
10
10 9 6 1 10 9 7 6 7 6 

correct output
6

user output
6

Test 10

Verdict: ACCEPTED

input
10
2 0 9 9 2 4 10 10 5 0 

correct output
3

user output
3

Test 11

Verdict: ACCEPTED

input
10
1 0 0 7 5 2 7 10 4 1 

correct output
2

user output
2

Test 12

Verdict: ACCEPTED

input
10
1 4 8 9 2 0 5 7 0 3 

correct output
2

user output
2

Test 13

Verdict: ACCEPTED

input
10
8 6 2 9 9 9 10 1 10 8 

correct output
6

user output
6

Test 14

Verdict: ACCEPTED

input
10
5 10 8 7 9 4 0 1 3 2 

correct output
3

user output
3

Test 15

Verdict: ACCEPTED

input
10
9 8 1 6 0 1 3 9 3 10 

correct output
3

user output
3

Test 16

Verdict: ACCEPTED

input
100
417 998 721 933 0 128 302 1000...

correct output
402

user output
402

Test 17

Verdict: ACCEPTED

input
100
436 185 25 932 550 948 435 485...

correct output
402

user output
402

Test 18

Verdict: ACCEPTED

input
100
551 70 708 840 291 121 511 569...

correct output
391

user output
391

Test 19

Verdict: ACCEPTED

input
100
967 901 547 172 973 856 715 60...

correct output
395

user output
395

Test 20

Verdict: ACCEPTED

input
100
222 55 871 832 206 364 919 980...

correct output
418

user output
418

Test 21

Verdict: ACCEPTED

input
100
180 68 19 665 463 194 725 927 ...

correct output
401

user output
401

Test 22

Verdict: ACCEPTED

input
100
154 446 740 874 263 86 534 724...

correct output
409

user output
409

Test 23

Verdict: ACCEPTED

input
100
778 607 237 860 825 893 966 17...

correct output
419

user output
419

Test 24

Verdict: ACCEPTED

input
100
514 922 773 659 871 366 8 149 ...

correct output
410

user output
410

Test 25

Verdict: ACCEPTED

input
100
849 814 179 591 54 111 361 819...

correct output
381

user output
381

Test 26

Verdict: ACCEPTED

input
100
48 800 289 680 721 36 21 952 2...

correct output
446

user output
446

Test 27

Verdict: ACCEPTED

input
100
208 702 482 731 420 638 860 78...

correct output
431

user output
431

Test 28

Verdict: ACCEPTED

input
100
517 669 947 185 766 782 282 57...

correct output
417

user output
417

Test 29

Verdict: ACCEPTED

input
100
960 294 700 52 1000 317 220 98...

correct output
483

user output
483

Test 30

Verdict: ACCEPTED

input
100
870 696 582 433 279 98 186 181...

correct output
433

user output
433

Test 31

Verdict: ACCEPTED

input
1000
549 593 715 845 603 858 545 84...

correct output
417

user output
417

Test 32

Verdict: ACCEPTED

input
1000
417 998 721 933 0 128 302 1000...

correct output
409

user output
409

Test 33

Verdict: ACCEPTED

input
1000
436 185 25 932 550 948 435 485...

correct output
409

user output
409

Test 34

Verdict: ACCEPTED

input
1000
551 70 708 840 291 121 511 569...

correct output
416

user output
416

Test 35

Verdict: ACCEPTED

input
1000
967 901 547 172 973 856 715 60...

correct output
420

user output
420

Test 36

Verdict: ACCEPTED

input
2000
238363352 59249203 934941691 8...

correct output
408637955

user output
408637955

Test 37

Verdict: ACCEPTED

input
2000
958701282 356460600 224848373 ...

correct output
419252506

user output
419252506

Test 38

Verdict: ACCEPTED

input
2000
81935403 244103473 837431430 3...

correct output
416082617

user output
416082617

Test 39

Verdict: ACCEPTED

input
2000
937837680 11934037 257096282 9...

correct output
417515719

user output
417515719

Test 40

Verdict: ACCEPTED

input
2000
11139167 391337047 538883743 5...

correct output
409258945

user output
409258945

Test 41

Verdict: ACCEPTED

input
10000
589284011 636562059 767928733 ...

correct output
413957321

user output
413957321

Test 42

Verdict: ACCEPTED

input
20000
447773961 773442531 122815 137...

correct output
414852078

user output
414852078

Test 43

Verdict: ACCEPTED

input
30000
468145962 198730371 27838075 5...

correct output
410179075

user output
410179075

Test 44

Verdict: ACCEPTED

input
40000
591414746 75940262 760367934 9...

correct output
414505355

user output
414505355

Test 45

Verdict: ACCEPTED

input
50000
967034923 587586157 185430193 ...

correct output
412022071

user output
412022071

Test 46

Verdict: ACCEPTED

input
60000
238363352 59249203 934941691 8...

correct output
414871380

user output
414871380

Test 47

Verdict: ACCEPTED

input
70000
958701282 356460600 224848373 ...

correct output
413955399

user output
413955399

Test 48

Verdict: ACCEPTED

input
80000
81935403 244103473 837431430 3...

correct output
414719178

user output
414719178

Test 49

Verdict: ACCEPTED

input
90000
937837680 11934037 257096282 9...

correct output
412407588

user output
412407588

Test 50

Verdict: ACCEPTED

input
100000
11139167 391337047 538883743 5...

correct output
413339299

user output
413339299

Test 51

Verdict: ACCEPTED

input
200000
589284011 636562059 767928733 ...

correct output
414309243

user output
414309243

Test 52

Verdict: ACCEPTED

input
200000
447773961 773442531 122815 137...

correct output
413259631

user output
413259631

Test 53

Verdict: ACCEPTED

input
200000
468145962 198730371 27838075 5...

correct output
413293056

user output
413293056

Test 54

Verdict: ACCEPTED

input
200000
591414746 75940262 760367934 9...

correct output
414827553

user output
414827553

Test 55

Verdict: ACCEPTED

input
200000
967034923 587586157 185430193 ...

correct output
412998578

user output
412998578