CSES - Datatähti 2018 loppu - Results
Submission details
Task:Metsämetro
Sender:Kuha
Submission time:2018-01-18 14:10:37 +0200
Language:C++
Status:READY
Result:42
Feedback
groupverdictscore
#1ACCEPTED14
#2ACCEPTED28
#30
Test results
testverdicttimegroup
#1ACCEPTED0.05 s1details
#2ACCEPTED0.05 s1details
#3ACCEPTED0.03 s1details
#4ACCEPTED0.03 s1details
#5ACCEPTED0.04 s1details
#6ACCEPTED0.06 s1details
#7ACCEPTED0.05 s1details
#8ACCEPTED0.04 s1details
#9ACCEPTED0.04 s1details
#10ACCEPTED0.05 s1details
#11ACCEPTED0.05 s2details
#12ACCEPTED0.05 s2details
#13ACCEPTED0.04 s2details
#14ACCEPTED0.06 s2details
#15ACCEPTED0.05 s2details
#16ACCEPTED0.04 s2details
#17ACCEPTED0.04 s2details
#18ACCEPTED0.04 s2details
#19ACCEPTED0.04 s2details
#20ACCEPTED0.05 s2details
#21ACCEPTED0.11 s3details
#22ACCEPTED0.13 s3details
#230.11 s3details
#24ACCEPTED0.13 s3details
#25ACCEPTED0.13 s3details
#26ACCEPTED0.11 s3details
#270.14 s3details
#280.13 s3details
#29ACCEPTED0.12 s3details
#30ACCEPTED0.12 s3details

Compiler report

input/code.cpp: In function 'bool ok(long long int)':
input/code.cpp:28:20: warning: unused variable 'o' [-Wunused-variable]
                 ll o = c;
                    ^
input/code.cpp:44:16: warning: unused variable 'o' [-Wunused-variable]
             ll o = c;
                ^
input/code.cpp: In function 'int main()':
input/code.cpp:65:8: warning: unused variable 'nc' [-Wunused-variable]
     ll nc = 0;
        ^
input/code.cpp:69:8: warning: unused variable 'temp' [-Wunused-variable]
     ll temp = 0;
        ^

Code

#include <bits/stdc++.h>
#define ll long long
#define N (1<<17)
#define pii pair<int, int>
#define F first
#define S second

using namespace std;

ll x[N];
ll s;
int n;
    
bool ok (ll k) {
    ll tr = s / 2;
    ll r = s;
    ll c = 0;
    //cout<<0<<" ";
    for (int i = 1; i <= n; i++) {
        ll q = x[i];
        if (c > k) return false;
        if (c > r) return false;
        if (c + q > r - q) {
            r -= q;
            ll t = min(r, k);
            if (c <= t) {
                if (q > 2 * c + t - c) return false;
                ll o = c;
                ll d = abs(c - t);
                c += min(q, d);
                q -= min(q, d);
                c -= q % 2;
                tr -= q / 2;
                //cout<<t<<"y";
            } else {
                //cout<<r<<"x";
                q -= c - r;
                c = r;
                if (c == 0 && q) return false;
                c -= q % 2;
            }
        } else { // c + x[i] <= r - x[i]
            if (q > 2 * c + k - c) return false;
            ll o = c;
            ll d = abs(c - k);
            c += min(q, d);
            q -= min(q, d);
            c -= q % 2;
            tr -= q / 2;
            r -= x[i];
        }
        //cout<<c<<" ";
    }
    //cout<<endl;
    return true;
}

int main () {
    cin>>n;
    for (int i = 1; i <= n; i++) {
        cin>>x[i];
        s += x[i];
    }
    ll mn = 0;
    ll nc = 0;
    ll xc = 0;
    ll mx = 0;
    bool xd = false;
    ll temp = 0;
    for (int i = 1; i <= n; i++) {
        if (!xd && xc + x[i] <= s / 2) {
            xc += x[i];
        } else if (!xd) {
            xd = true;
            xc = s / 2 - (x[i] - (s / 2 - xc)); 
        } else {
            xc -= x[i];
        }
        mx = max(mx, xc);
    }
    
    //for (int i = 1; i <= s / 2; i++) cout<<ok(i)<<" ";
    //cout<<endl;
 //ok(8);
 //cout<<endl;
    //ok(10);
   // cout<<endl;
    //return 0;
    
    for (ll i = s / 2; i >= 1; i /= 2) {
        //cout<<(mn + i <= s / 2)<<" "<<(!ok(mn + i))<<" "<<mn+i<<endl;
        while (mn + i <= s / 2 && !ok(mn + i)) mn += i;
    }
    mn++;
    cout<<mn<<" "<<mx<<endl;
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
10
9 4 9 7 6 10 4 6 2 9

correct output
9 31

user output
9 31

Test 2

Group: 1

Verdict: ACCEPTED

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

correct output
10 25

user output
10 25

Test 3

Group: 1

Verdict: ACCEPTED

input
10
10 2 4 1 4 9 6 3 5 10

correct output
10 24

user output
10 24

Test 4

Group: 1

Verdict: ACCEPTED

input
10
7 5 1 3 8 4 5 4 6 3

correct output
7 22

user output
7 22

Test 5

Group: 1

Verdict: ACCEPTED

input
10
10 7 8 4 10 6 8 6 2 3

correct output
10 29

user output
10 29

Test 6

Group: 1

Verdict: ACCEPTED

input
10
1 2 8 2 3 1 3 1 4 9

correct output
9 17

user output
9 17

Test 7

Group: 1

Verdict: ACCEPTED

input
10
2 8 2 5 8 8 5 10 9 7

correct output
7 31

user output
7 31

Test 8

Group: 1

Verdict: ACCEPTED

input
10
2 10 4 8 10 10 9 3 9 7

correct output
8 34

user output
8 34

Test 9

Group: 1

Verdict: ACCEPTED

input
10
10 7 9 1 7 8 4 4 1 5

correct output
10 27

user output
10 27

Test 10

Group: 1

Verdict: ACCEPTED

input
10
1 4 7 7 3 1 10 6 4 3

correct output
5 23

user output
5 23

Test 11

Group: 2

Verdict: ACCEPTED

input
100
5 3 4 7 5 1 7 1 6 10 2 9 6 5 9...

correct output
6 281

user output
6 281

Test 12

Group: 2

Verdict: ACCEPTED

input
100
3 9 7 3 6 6 4 3 1 8 2 4 2 6 2 ...

correct output
7 252

user output
7 252

Test 13

Group: 2

Verdict: ACCEPTED

input
100
8 2 3 4 8 3 2 7 10 10 3 2 3 4 ...

correct output
8 252

user output
8 252

Test 14

Group: 2

Verdict: ACCEPTED

input
100
4 4 9 8 5 6 2 3 7 10 10 2 7 5 ...

correct output
9 261

user output
9 261

Test 15

Group: 2

Verdict: ACCEPTED

input
100
7 3 3 5 10 6 6 8 10 5 5 8 3 5 ...

correct output
10 300

user output
10 300

Test 16

Group: 2

Verdict: ACCEPTED

input
100
9 5 2 1 9 8 6 4 1 6 3 5 3 1 4 ...

correct output
9 289

user output
9 289

Test 17

Group: 2

Verdict: ACCEPTED

input
100
9 7 5 5 4 1 9 2 3 5 10 2 10 5 ...

correct output
9 287

user output
9 287

Test 18

Group: 2

Verdict: ACCEPTED

input
100
3 8 5 10 8 10 9 2 8 3 1 2 9 7 ...

correct output
6 282

user output
6 282

Test 19

Group: 2

Verdict: ACCEPTED

input
100
6 3 9 2 8 7 8 4 6 4 4 10 2 10 ...

correct output
8 260

user output
8 260

Test 20

Group: 2

Verdict: ACCEPTED

input
100
10 8 7 8 10 3 1 2 1 1 7 4 5 5 ...

correct output
10 279

user output
10 279

Test 21

Group: 3

Verdict: ACCEPTED

input
100000
917855934 394938644 81692499 4...

correct output
917855934 23490295363738

user output
917855934 23490295363738

Test 22

Group: 3

Verdict: ACCEPTED

input
100000
898177957 193852227 11785863 3...

correct output
898177957 23488890808371

user output
898177957 23488890808371

Test 23

Group: 3

Verdict:

input
100000
560743028 996665755 25721760 4...

correct output
576170439 23599624330076

user output
560743028 23599624330076

Test 24

Group: 3

Verdict: ACCEPTED

input
100000
836491959 800539061 666447484 ...

correct output
836491959 23450143338851

user output
836491959 23450143338851

Test 25

Group: 3

Verdict: ACCEPTED

input
100000
156445358 170997055 927078622 ...

correct output
930838017 23503313036290

user output
930838017 23503313036290

Test 26

Group: 3

Verdict: ACCEPTED

input
100000
869942654 614144284 154904581 ...

correct output
869942654 23544105883410

user output
869942654 23544105883410

Test 27

Group: 3

Verdict:

input
100000
471025024 244072220 419574192 ...

correct output
657776925 23597080152723

user output
499998357 23597080152723

Test 28

Group: 3

Verdict:

input
100000
561299091 285120535 109702008 ...

correct output
862325964 23517085653307

user output
561299091 23517085653307

Test 29

Group: 3

Verdict: ACCEPTED

input
100000
356879006 3017698 603259365 18...

correct output
499995467 23540251578008

user output
499995467 23540251578008

Test 30

Group: 3

Verdict: ACCEPTED

input
100000
190109479 83895435 595795373 8...

correct output
598676555 23565408317817

user output
598676555 23565408317817