Task: | Old legos |
Sender: | aalto2024b_002 |
Submission time: | 2024-09-11 17:49:22 +0300 |
Language: | C++ (C++20) |
Status: | READY |
Result: | WRONG ANSWER |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.00 s | details |
#2 | ACCEPTED | 0.00 s | details |
#3 | ACCEPTED | 0.00 s | details |
#4 | ACCEPTED | 0.00 s | details |
#5 | ACCEPTED | 0.00 s | details |
#6 | ACCEPTED | 0.00 s | details |
#7 | ACCEPTED | 0.00 s | details |
#8 | ACCEPTED | 0.00 s | details |
#9 | ACCEPTED | 0.00 s | details |
#10 | ACCEPTED | 0.00 s | details |
#11 | ACCEPTED | 0.00 s | details |
#12 | ACCEPTED | 0.00 s | details |
#13 | ACCEPTED | 0.00 s | details |
#14 | ACCEPTED | 0.00 s | details |
#15 | ACCEPTED | 0.00 s | details |
#16 | ACCEPTED | 0.00 s | details |
#17 | ACCEPTED | 0.00 s | details |
#18 | ACCEPTED | 0.00 s | details |
#19 | ACCEPTED | 0.00 s | details |
#20 | WRONG ANSWER | 0.01 s | details |
#21 | ACCEPTED | 0.80 s | details |
#22 | TIME LIMIT EXCEEDED | -- | details |
#23 | WRONG ANSWER | 0.08 s | details |
#24 | ACCEPTED | 0.80 s | details |
#25 | TIME LIMIT EXCEEDED | -- | details |
#26 | ACCEPTED | 0.80 s | details |
#27 | TIME LIMIT EXCEEDED | -- | details |
#28 | ACCEPTED | 0.80 s | details |
#29 | TIME LIMIT EXCEEDED | -- | details |
#30 | TIME LIMIT EXCEEDED | -- | details |
#31 | TIME LIMIT EXCEEDED | -- | details |
#32 | TIME LIMIT EXCEEDED | -- | details |
#33 | TIME LIMIT EXCEEDED | -- | details |
#34 | TIME LIMIT EXCEEDED | -- | details |
#35 | TIME LIMIT EXCEEDED | -- | details |
#36 | TIME LIMIT EXCEEDED | -- | details |
#37 | TIME LIMIT EXCEEDED | -- | details |
#38 | TIME LIMIT EXCEEDED | -- | details |
#39 | TIME LIMIT EXCEEDED | -- | details |
#40 | TIME LIMIT EXCEEDED | -- | details |
#41 | TIME LIMIT EXCEEDED | -- | details |
#42 | TIME LIMIT EXCEEDED | -- | details |
#43 | TIME LIMIT EXCEEDED | -- | details |
#44 | TIME LIMIT EXCEEDED | -- | details |
#45 | TIME LIMIT EXCEEDED | -- | details |
#46 | TIME LIMIT EXCEEDED | -- | details |
#47 | TIME LIMIT EXCEEDED | -- | details |
#48 | TIME LIMIT EXCEEDED | -- | details |
#49 | TIME LIMIT EXCEEDED | -- | details |
#50 | TIME LIMIT EXCEEDED | -- | details |
#51 | TIME LIMIT EXCEEDED | -- | details |
#52 | TIME LIMIT EXCEEDED | -- | details |
#53 | TIME LIMIT EXCEEDED | -- | details |
#54 | TIME LIMIT EXCEEDED | -- | details |
#55 | TIME LIMIT EXCEEDED | -- | details |
#56 | TIME LIMIT EXCEEDED | -- | details |
#57 | TIME LIMIT EXCEEDED | -- | details |
#58 | TIME LIMIT EXCEEDED | -- | details |
#59 | TIME LIMIT EXCEEDED | -- | details |
#60 | RUNTIME ERROR | 0.87 s | details |
#61 | RUNTIME ERROR | 0.88 s | details |
#62 | RUNTIME ERROR | 0.88 s | details |
#63 | RUNTIME ERROR | 0.87 s | details |
#64 | RUNTIME ERROR | 0.87 s | details |
#65 | RUNTIME ERROR | 0.88 s | details |
#66 | RUNTIME ERROR | 0.87 s | details |
#67 | RUNTIME ERROR | 0.88 s | details |
#68 | RUNTIME ERROR | 0.87 s | details |
#69 | RUNTIME ERROR | 0.89 s | details |
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: WRONG ANSWER
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: TIME LIMIT EXCEEDED
input |
---|
11 198730372 27838076 590195590 467423861 520495379 451366491 344173378 354694313 ... |
correct output |
---|
1075637330 |
user output |
---|
(empty) |
Test 23
Verdict: WRONG ANSWER
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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
input |
---|
11 391337048 538883744 535937150 532332526 8099343 143698367 339543270 152590624 ... |
correct output |
---|
246913369 |
user output |
---|
(empty) |
Test 30
Verdict: TIME LIMIT EXCEEDED
input |
---|
101 3 906523441 3 585063857 454895875 2 2 469855690 ... |
correct output |
---|
-1950121670 |
user output |
---|
(empty) |
Test 31
Verdict: TIME LIMIT EXCEEDED
input |
---|
100 773442532 122816 137572579 324627123 157577940 253498609 99147813 425825313 ... |
correct output |
---|
2484533534 |
user output |
---|
(empty) |
Test 32
Verdict: TIME LIMIT EXCEEDED
input |
---|
100 198730372 27838076 590195590 467423861 520495379 451366491 344173378 354694313 ... |
correct output |
---|
1162250085 |
user output |
---|
(empty) |
Test 33
Verdict: TIME LIMIT EXCEEDED
input |
---|
100 760367935 901888417 130275571 548496961 3 469291685 20130523 1 ... |
correct output |
---|
-513884705 |
user output |
---|
(empty) |
Test 34
Verdict: TIME LIMIT EXCEEDED
input |
---|
100 587586158 1 918715995 3 3 641621091 151896000 241061404 ... |
correct output |
---|
4449680753 |
user output |
---|
(empty) |
Test 35
Verdict: TIME LIMIT EXCEEDED
input |
---|
100 59249204 934941692 892631472 221963002 390559518 986350949 524427523 96444602 ... |
correct output |
---|
2289597915 |
user output |
---|
(empty) |
Test 36
Verdict: TIME LIMIT EXCEEDED
input |
---|
101 356460601 1 68992860 1 1 638932295 568887059 653343572 ... |
correct output |
---|
-1011275811 |
user output |
---|
(empty) |
Test 37
Verdict: TIME LIMIT EXCEEDED
input |
---|
100 244103474 837431431 342493822 470738321 776814822 489180570 330726191 578205540 ... |
correct output |
---|
-3347612884 |
user output |
---|
(empty) |
Test 38
Verdict: TIME LIMIT EXCEEDED
input |
---|
100 257096283 933290530 2 876668629 453495728 12239373 2 822553808 ... |
correct output |
---|
-5234322969 |
user output |
---|
(empty) |
Test 39
Verdict: TIME LIMIT EXCEEDED
input |
---|
101 391337048 538883744 535937150 532332526 8099343 143698367 339543270 152590624 ... |
correct output |
---|
1057263569 |
user output |
---|
(empty) |
Test 40
Verdict: TIME LIMIT EXCEEDED
input |
---|
200 3 906523441 3 585063857 454895875 2 2 469855690 ... |
correct output |
---|
-1859110273 |
user output |
---|
(empty) |
Test 41
Verdict: TIME LIMIT EXCEEDED
input |
---|
201 773442532 122816 137572579 324627123 157577940 253498609 99147813 425825313 ... |
correct output |
---|
-1706556434 |
user output |
---|
(empty) |
Test 42
Verdict: TIME LIMIT EXCEEDED
input |
---|
200 198730372 27838076 590195590 467423861 520495379 451366491 344173378 354694313 ... |
correct output |
---|
2881192575 |
user output |
---|
(empty) |
Test 43
Verdict: TIME LIMIT EXCEEDED
input |
---|
200 760367935 901888417 130275571 548496961 3 469291685 20130523 1 ... |
correct output |
---|
367410203 |
user output |
---|
(empty) |
Test 44
Verdict: TIME LIMIT EXCEEDED
input |
---|
201 587586158 1 918715995 3 3 641621091 151896000 241061404 ... |
correct output |
---|
6064184122 |
user output |
---|
(empty) |
Test 45
Verdict: TIME LIMIT EXCEEDED
input |
---|
200 59249204 934941692 892631472 221963002 390559518 986350949 524427523 96444602 ... |
correct output |
---|
-541796892 |
user output |
---|
(empty) |
Test 46
Verdict: TIME LIMIT EXCEEDED
input |
---|
200 356460601 1 68992860 1 1 638932295 568887059 653343572 ... |
correct output |
---|
-3818748427 |
user output |
---|
(empty) |
Test 47
Verdict: TIME LIMIT EXCEEDED
input |
---|
201 244103474 837431431 342493822 470738321 776814822 489180570 330726191 578205540 ... |
correct output |
---|
1128073230 |
user output |
---|
(empty) |
Test 48
Verdict: TIME LIMIT EXCEEDED
input |
---|
200 257096283 933290530 2 876668629 453495728 12239373 2 822553808 ... |
correct output |
---|
-4097764173 |
user output |
---|
(empty) |
Test 49
Verdict: TIME LIMIT EXCEEDED
input |
---|
201 391337048 538883744 535937150 532332526 8099343 143698367 339543270 152590624 ... |
correct output |
---|
4209206317 |
user output |
---|
(empty) |
Test 50
Verdict: TIME LIMIT EXCEEDED
input |
---|
1001 3 906523441 3 585063857 454895875 2 2 469855690 ... |
correct output |
---|
797530744 |
user output |
---|
(empty) |
Test 51
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 773442532 122816 137572579 324627123 157577940 253498609 99147813 425825313 ... |
correct output |
---|
-6859401550 |
user output |
---|
(empty) |
Test 52
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 198730372 27838076 590195590 467423861 520495379 451366491 344173378 354694313 ... |
correct output |
---|
3341433705 |
user output |
---|
(empty) |
Test 53
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 760367935 901888417 130275571 548496961 3 469291685 20130523 1 ... |
correct output |
---|
3932941646 |
user output |
---|
(empty) |
Test 54
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 587586158 1 918715995 3 3 641621091 151896000 241061404 ... |
correct output |
---|
12940904658 |
user output |
---|
(empty) |
Test 55
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 59249204 934941692 892631472 221963002 390559518 986350949 524427523 96444602 ... |
correct output |
---|
-11353638361 |
user output |
---|
(empty) |
Test 56
Verdict: TIME LIMIT EXCEEDED
input |
---|
1001 356460601 1 68992860 1 1 638932295 568887059 653343572 ... |
correct output |
---|
196162653 |
user output |
---|
(empty) |
Test 57
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 244103474 837431431 342493822 470738321 776814822 489180570 330726191 578205540 ... |
correct output |
---|
8993059628 |
user output |
---|
(empty) |
Test 58
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 257096283 933290530 2 876668629 453495728 12239373 2 822553808 ... |
correct output |
---|
-11284740290 |
user output |
---|
(empty) |
Test 59
Verdict: TIME LIMIT EXCEEDED
input |
---|
1001 391337048 538883744 535937150 532332526 8099343 143698367 339543270 152590624 ... |
correct output |
---|
12730443353 |
user output |
---|
(empty) |
Test 60
Verdict: RUNTIME ERROR
input |
---|
100000 3 906523441 3 585063857 454895875 2 2 469855690 ... |
correct output |
---|
105607728400 |
user output |
---|
(empty) |
Test 61
Verdict: RUNTIME ERROR
input |
---|
100000 773442532 122816 137572579 324627123 157577940 253498609 99147813 425825313 ... |
correct output |
---|
21174476635 |
user output |
---|
(empty) |
Test 62
Verdict: RUNTIME ERROR
input |
---|
100000 198730372 27838076 590195590 467423861 520495379 451366491 344173378 354694313 ... |
correct output |
---|
65624350916 |
user output |
---|
(empty) |
Test 63
Verdict: RUNTIME ERROR
input |
---|
100000 760367935 901888417 130275571 548496961 3 469291685 20130523 1 ... |
correct output |
---|
66836037029 |
user output |
---|
(empty) |
Test 64
Verdict: RUNTIME ERROR
input |
---|
100000 587586158 1 918715995 3 3 641621091 151896000 241061404 ... |
correct output |
---|
-87105533715 |
user output |
---|
(empty) |
Test 65
Verdict: RUNTIME ERROR
input |
---|
100000 59249204 934941692 892631472 221963002 390559518 986350949 524427523 96444602 ... |
correct output |
---|
-1093858395 |
user output |
---|
(empty) |
Test 66
Verdict: RUNTIME ERROR
input |
---|
99999 356460601 1 68992860 1 1 638932295 568887059 653343572 ... |
correct output |
---|
-28178672820 |
user output |
---|
(empty) |
Test 67
Verdict: RUNTIME ERROR
input |
---|
99999 244103474 837431431 342493822 470738321 776814822 489180570 330726191 578205540 ... |
correct output |
---|
72715249868 |
user output |
---|
(empty) |
Test 68
Verdict: RUNTIME ERROR
input |
---|
99999 257096283 933290530 2 876668629 453495728 12239373 2 822553808 ... |
correct output |
---|
-46790665125 |
user output |
---|
(empty) |
Test 69
Verdict: RUNTIME ERROR
input |
---|
99999 391337048 538883744 535937150 532332526 8099343 143698367 339543270 152590624 ... |
correct output |
---|
12190306919 |
user output |
---|
(empty) |