CSES - Aalto Competitive Programming 2024 - wk2 - Wed - Results
Submission details
Task:Old legos
Sender:aalto2024b_002
Submission time:2024-09-11 17:49:22 +0300
Language:C++ (C++20)
Status:READY
Result:
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
#200.01 sdetails
#21ACCEPTED0.80 sdetails
#22--details
#230.08 sdetails
#24ACCEPTED0.80 sdetails
#25--details
#26ACCEPTED0.80 sdetails
#27--details
#28ACCEPTED0.80 sdetails
#29--details
#30--details
#31--details
#32--details
#33--details
#34--details
#35--details
#36--details
#37--details
#38--details
#39--details
#40--details
#41--details
#42--details
#43--details
#44--details
#45--details
#46--details
#47--details
#48--details
#49--details
#50--details
#51--details
#52--details
#53--details
#54--details
#55--details
#56--details
#57--details
#58--details
#59--details
#600.87 sdetails
#610.88 sdetails
#620.88 sdetails
#630.87 sdetails
#640.87 sdetails
#650.88 sdetails
#660.87 sdetails
#670.88 sdetails
#680.87 sdetails
#690.89 sdetails

Code

#include <algorithm>
#include <iostream>
#include <limits>
#include <set>
#include <utility>
#include <vector>

/**
Uolevi and Maija are visiting their parents. While the blueberry pie is cooking
in the oven, they go explore the attic. They find their old legos and decide to
build castles from them. There are n legos in a box numbered 1,2,\dots,n, the
i-th of which has u_i nostalgic value to Uolevi and m_i to Maija. The siblings
then take turns in picking legos from the box and placing them to their castles.
Naturally, both try to maximize the value difference between their own castle
and their opponents castle. Formally, the legos will be divided into two sets U
and M at the end of the process. Uolevi's castle has value x = \sum_{i \in
U}{u_i} and Maija's castle has value y = \sum_{i \in M}{m_i}. Maija tries to
minimize x-y while Uolevi tries to maximize it. Calculate x-y if Uolevi gets to
pick the first lego and both pick the legos optimally.

Input
First line contain a single integer n.
The 𝑖-th of the next n lines contains two integers u_i and m_𝑖.

Output
Output a single integer x-y.
Constraints

1 \leq n \leq 10^5
1 \leq u_i, m_i \leq 10^9

Example 1
Input:
5
3 1
9 3
6 3
2 10
1 7

Output:
1

Explanation:
The sequence of picks would be:
Uolevi picks lego 2
Maija picks lego 4
Uolevi picks lego 3
Maija picks lego 5
Uolevi picks lego 1
Example 2
Input:
2
10 2
1 1000

Output:
-1
 */

using namespace std;

const int INF = numeric_limits<int>::max();
const int NEGINF = numeric_limits<int>::lowest();

template <typename T>
std::ostream &operator<<(std::ostream &os, const vector<T> &obj) {
    bool first = true;
    for (const auto &o : obj) {
        if (first) {
            cout << o;
            first = false;
        } else {
            cout << ' ' << o;
        }
    }
    cout << endl;
    return os;
}

std::ostream &operator<<(std::ostream &os, const vector<pair<int, int>> &obj) {
    for (const auto &o : obj) {
        cout << o.first << ' ' << o.second << endl;
    }
    cout << endl;
    return os;
}

vector<pair<int, int>> UM;

int u(set<pair<int, int>> &left);

int m(set<pair<int, int>> left) {
    if (left.empty())
        return 0;
    if (left.size() == 1)
        return -left.begin()->second;

    int best = INF;

    auto scratch{left};
    for (auto &elem : left) {
        scratch.erase(elem);
        int u_ = u(scratch);
        if (-elem.second + u_ < best)
            best = -elem.second + u_;
        scratch.insert(elem);
    }
    return best;
}

int u(set<pair<int, int>> &left) {
    if (left.empty())
        return 0;
    if (left.size() == 1)
        return left.begin()->first;

    int best = NEGINF;

    auto scratch{left};
    for (auto &elem : left) {
        scratch.erase(elem);
        int m_ = m(scratch);
        if (elem.first + m_ > best)
            best = elem.first + m_;
        scratch.insert(elem);
    }
    return best;
}

int main(int argc, char **argv) {
    int n;
    cin >> n;

    UM = vector<pair<int, int>>(n);

    for (int i = 0; i < n; ++i) {
        cin >> UM[i].first;
        cin >> UM[i].second;
    }
    set<pair<int, int>> left{UM.begin(), UM.end()};

    cout << u(left);

    // sort(UM.begin(), UM.end(), [](pair<int, int> a, pair<int, int> b) {
    //     return abs(a.first - a.second) > abs(b.first - b.second);
    // });
    //
    // cout << endl;
    // cout << "UM: " << endl << UM << endl;
    // char turn{'U'};
    // int x_y = 0;
    // for (int i = 0; i < UM.size(); ++i) {
    //     if (turn == 'U') {
    //         x_y += UM[i].first;
    //         turn = 'M';
    //     } else {
    //         x_y -= UM[i].second;
    //         turn = 'U';
    //     }
    // }
    // cout << x_y << endl;
}

Test details

Test 1

Verdict: ACCEPTED

input
1
9 2

correct output
9

user output
9

Test 2

Verdict: ACCEPTED

input
1
10 4

correct output
10

user output
10

Test 3

Verdict: ACCEPTED

input
2
8 1
3 5

correct output
3

user output
3

Test 4

Verdict: ACCEPTED

input
2
2 9
3 10

correct output
-6

user output
-6

Test 5

Verdict: ACCEPTED

input
3
7 2
6 2
2 3

correct output
7

user output
7

Test 6

Verdict: ACCEPTED

input
3
3 2
7 9
3 8

correct output
2

user output
2

Test 7

Verdict: ACCEPTED

input
4
5 10
9 9
1 10
8 8

correct output
-4

user output
-4

Test 8

Verdict: ACCEPTED

input
4
3 2
7 9
3 8
4 6

correct output
1

user output
1

Test 9

Verdict: ACCEPTED

input
4
5 3
8 1
9 1
3 3

correct output
10

user output
10

Test 10

Verdict: ACCEPTED

input
5
3 9
3 6
5 2
2 5
...

correct output
5

user output
5

Test 11

Verdict: ACCEPTED

input
5
10 8
10 1
2 4
10 2
...

correct output
17

user output
17

Test 12

Verdict: ACCEPTED

input
5
2 1
10 6
10 5
5 5
...

correct output
8

user output
8

Test 13

Verdict: ACCEPTED

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

correct output
3

user output
3

Test 14

Verdict: ACCEPTED

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

correct output
1

user output
1

Test 15

Verdict: ACCEPTED

input
5
1 9
9 3
4 10
10 5
...

correct output
1

user output
1

Test 16

Verdict: ACCEPTED

input
5
4 1
1 1
1 10
1 6
...

correct output
-4

user output
-4

Test 17

Verdict: ACCEPTED

input
5
3 8
4 5
10 8
5 10
...

correct output
1

user output
1

Test 18

Verdict: ACCEPTED

input
5
10 3
4 2
3 2
7 5
...

correct output
11

user output
11

Test 19

Verdict: ACCEPTED

input
5
4 6
5 5
1 2
4 2
...

correct output
1

user output
1

Test 20

Verdict:

input
10
3 9
3 6
5 2
2 5
...

correct output
-5

user output
1

Test 21

Verdict: ACCEPTED

input
10
10 8
10 1
2 4
10 2
...

correct output
20

user output
20

Test 22

Verdict:

input
11
198730372 27838076
590195590 467423861
520495379 451366491
344173378 354694313
...

correct output
1075637330

user output
(empty)

Test 23

Verdict:

input
10
8 9
2 6
3 5
1 1
...

correct output
-3

user output
-2

Test 24

Verdict: ACCEPTED

input
10
6 1
9 3
3 6
2 10
...

correct output
-2

user output
-2

Test 25

Verdict:

input
11
59249204 934941692
892631472 221963002
390559518 986350949
524427523 96444602
...

correct output
1389122128

user output
(empty)

Test 26

Verdict: ACCEPTED

input
10
4 1
1 1
1 10
1 6
...

correct output
-6

user output
-6

Test 27

Verdict:

input
11
244103474 837431431
342493822 470738321
776814822 489180570
330726191 578205540
...

correct output
-124259424

user output
(empty)

Test 28

Verdict: ACCEPTED

input
10
10 3
4 2
3 2
7 5
...

correct output
4

user output
4

Test 29

Verdict:

input
11
391337048 538883744
535937150 532332526
8099343 143698367
339543270 152590624
...

correct output
246913369

user output
(empty)

Test 30

Verdict:

input
101
3 906523441
3 585063857
454895875 2
2 469855690
...

correct output
-1950121670

user output
(empty)

Test 31

Verdict:

input
100
773442532 122816
137572579 324627123
157577940 253498609
99147813 425825313
...

correct output
2484533534

user output
(empty)

Test 32

Verdict:

input
100
198730372 27838076
590195590 467423861
520495379 451366491
344173378 354694313
...

correct output
1162250085

user output
(empty)

Test 33

Verdict:

input
100
760367935 901888417
130275571 548496961
3 469291685
20130523 1
...

correct output
-513884705

user output
(empty)

Test 34

Verdict:

input
100
587586158 1
918715995 3
3 641621091
151896000 241061404
...

correct output
4449680753

user output
(empty)

Test 35

Verdict:

input
100
59249204 934941692
892631472 221963002
390559518 986350949
524427523 96444602
...

correct output
2289597915

user output
(empty)

Test 36

Verdict:

input
101
356460601 1
68992860 1
1 638932295
568887059 653343572
...

correct output
-1011275811

user output
(empty)

Test 37

Verdict:

input
100
244103474 837431431
342493822 470738321
776814822 489180570
330726191 578205540
...

correct output
-3347612884

user output
(empty)

Test 38

Verdict:

input
100
257096283 933290530
2 876668629
453495728 12239373
2 822553808
...

correct output
-5234322969

user output
(empty)

Test 39

Verdict:

input
101
391337048 538883744
535937150 532332526
8099343 143698367
339543270 152590624
...

correct output
1057263569

user output
(empty)

Test 40

Verdict:

input
200
3 906523441
3 585063857
454895875 2
2 469855690
...

correct output
-1859110273

user output
(empty)

Test 41

Verdict:

input
201
773442532 122816
137572579 324627123
157577940 253498609
99147813 425825313
...

correct output
-1706556434

user output
(empty)

Test 42

Verdict:

input
200
198730372 27838076
590195590 467423861
520495379 451366491
344173378 354694313
...

correct output
2881192575

user output
(empty)

Test 43

Verdict:

input
200
760367935 901888417
130275571 548496961
3 469291685
20130523 1
...

correct output
367410203

user output
(empty)

Test 44

Verdict:

input
201
587586158 1
918715995 3
3 641621091
151896000 241061404
...

correct output
6064184122

user output
(empty)

Test 45

Verdict:

input
200
59249204 934941692
892631472 221963002
390559518 986350949
524427523 96444602
...

correct output
-541796892

user output
(empty)

Test 46

Verdict:

input
200
356460601 1
68992860 1
1 638932295
568887059 653343572
...

correct output
-3818748427

user output
(empty)

Test 47

Verdict:

input
201
244103474 837431431
342493822 470738321
776814822 489180570
330726191 578205540
...

correct output
1128073230

user output
(empty)

Test 48

Verdict:

input
200
257096283 933290530
2 876668629
453495728 12239373
2 822553808
...

correct output
-4097764173

user output
(empty)

Test 49

Verdict:

input
201
391337048 538883744
535937150 532332526
8099343 143698367
339543270 152590624
...

correct output
4209206317

user output
(empty)

Test 50

Verdict:

input
1001
3 906523441
3 585063857
454895875 2
2 469855690
...

correct output
797530744

user output
(empty)

Test 51

Verdict:

input
1000
773442532 122816
137572579 324627123
157577940 253498609
99147813 425825313
...

correct output
-6859401550

user output
(empty)

Test 52

Verdict:

input
1000
198730372 27838076
590195590 467423861
520495379 451366491
344173378 354694313
...

correct output
3341433705

user output
(empty)

Test 53

Verdict:

input
1000
760367935 901888417
130275571 548496961
3 469291685
20130523 1
...

correct output
3932941646

user output
(empty)

Test 54

Verdict:

input
1000
587586158 1
918715995 3
3 641621091
151896000 241061404
...

correct output
12940904658

user output
(empty)

Test 55

Verdict:

input
1000
59249204 934941692
892631472 221963002
390559518 986350949
524427523 96444602
...

correct output
-11353638361

user output
(empty)

Test 56

Verdict:

input
1001
356460601 1
68992860 1
1 638932295
568887059 653343572
...

correct output
196162653

user output
(empty)

Test 57

Verdict:

input
1000
244103474 837431431
342493822 470738321
776814822 489180570
330726191 578205540
...

correct output
8993059628

user output
(empty)

Test 58

Verdict:

input
1000
257096283 933290530
2 876668629
453495728 12239373
2 822553808
...

correct output
-11284740290

user output
(empty)

Test 59

Verdict:

input
1001
391337048 538883744
535937150 532332526
8099343 143698367
339543270 152590624
...

correct output
12730443353

user output
(empty)

Test 60

Verdict:

input
100000
3 906523441
3 585063857
454895875 2
2 469855690
...

correct output
105607728400

user output
(empty)

Test 61

Verdict:

input
100000
773442532 122816
137572579 324627123
157577940 253498609
99147813 425825313
...

correct output
21174476635

user output
(empty)

Test 62

Verdict:

input
100000
198730372 27838076
590195590 467423861
520495379 451366491
344173378 354694313
...

correct output
65624350916

user output
(empty)

Test 63

Verdict:

input
100000
760367935 901888417
130275571 548496961
3 469291685
20130523 1
...

correct output
66836037029

user output
(empty)

Test 64

Verdict:

input
100000
587586158 1
918715995 3
3 641621091
151896000 241061404
...

correct output
-87105533715

user output
(empty)

Test 65

Verdict:

input
100000
59249204 934941692
892631472 221963002
390559518 986350949
524427523 96444602
...

correct output
-1093858395

user output
(empty)

Test 66

Verdict:

input
99999
356460601 1
68992860 1
1 638932295
568887059 653343572
...

correct output
-28178672820

user output
(empty)

Test 67

Verdict:

input
99999
244103474 837431431
342493822 470738321
776814822 489180570
330726191 578205540
...

correct output
72715249868

user output
(empty)

Test 68

Verdict:

input
99999
257096283 933290530
2 876668629
453495728 12239373
2 822553808
...

correct output
-46790665125

user output
(empty)

Test 69

Verdict:

input
99999
391337048 538883744
535937150 532332526
8099343 143698367
339543270 152590624
...

correct output
12190306919

user output
(empty)