— Dark mode

Datatähti 2024 alku

Uolevin kalansaalis

  • Start: 2023-10-30 00:00:00
  • End: 2023-11-13 00:00:00
CSES - Datatähti 2024 alku - Results
Submission details
Task:Uolevin kalansaalis
Sender:Username*
Submission time:2023-11-02 16:50:47 +0200
Language:C++ (C++20)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
Test results
testverdicttimegroup
#10.00 s1, 2details
#20.00 s1, 2details
#30.00 s1, 2details
#40.00 s1, 2details
#50.00 s1, 2details
#60.00 s1, 2details
#70.00 s1, 2details
#80.00 s1, 2details
#90.00 s1, 2details
#100.00 s1, 2details
#110.00 s1, 2details
#120.00 s1, 2details
#130.00 s1, 2details
#140.00 s1, 2details
#150.00 s1, 2details
#160.00 s2details
#170.00 s2details
#180.00 s2details
#190.00 s2details
#200.00 s2details
#210.00 s2details
#220.00 s2details
#230.00 s2details
#240.00 s2details

Compiler report

input/code.cpp:126:21: warning: "/*" within comment [-Wcomment]
  126 |                     /*for (Cell& cell : it->second) {
      |                      
input/code.cpp: In function 'int main()':
input/code.cpp:39:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>

using namespace std;

typedef long long int ll;

struct Cell {
    int row;
    int column;
    int value;
};


template<typename T>
struct sort_pair {
    bool operator()(const pair<int, T>& left, const pair<int, T>& right) {
        return left.first < right.first;
    }
};

template <
    class result_t = std::chrono::milliseconds,
    class clock_t = std::chrono::steady_clock,
    class duration_t = std::chrono::milliseconds
>
auto since(std::chrono::time_point<clock_t, duration_t> const& start)
{
    return std::chrono::duration_cast<result_t>(clock_t::now() - start);
}

int answer;
ll totalscore;
ll maxtri = 0;

int main() {
    freopen("input.txt", "r", stdin);

    //auto start = std::chrono::steady_clock::now();

    int n, m, k;
    cin >> n;
    cin >> m;
    cin >> k;

    if (k == 0 || (n == 1 && m == 1)) {
        cout << 0 << "\n";
        return 0;
    }

    vector<vector<Cell>> rows(n); // vec of rows of cells in order
    //cout << rows.size();

    //auto start = std::chrono::steady_clock::now();
    for (int i = 0; i < k; ++i) {
        int row, column;
        char fish;
        cin >> row; row -= 1;
        cin >> column; column -= 1;
        cin >> fish;
        int value;
        if (fish == 'K') {
            value = 10;
        }
        else {
            value = -1;
        }
        totalscore -= value;
        Cell c;
        c.row = row; c.column = column; c.value = value;

        rows[row].push_back(c);
    }

    for (vector<Cell>& row : rows) {
        sort(row.begin(), row.end(), [](auto& x, auto& y) { return (x.column < y.column); });
    }

    //auto start2 = std::chrono::steady_clock::now();
    bool even = false;
    //int debugitercount = 0;
    for (int i = 1; i <= n; ++i) { // i, n height
        //cout << i << "\n";
        for (int j = 1; j <= m; ++j) { // j, m width
            //cout << "\n\nstarting " << i << " " << j;
            int maxT, minT;
            if (!even) { // odd <
                // TODO: Issue with maxT?
                maxT = max(0, min({ i - 1, (j - 1) * 2, (m - j) * 2 + 1 })); // top, left, right
                minT = max(0, min({ n - i, (j - 1) * 2, (m - j) * 2 + 1 })); // bottom, left, right
            }
            else { // even >
                maxT = max(0, min({ i - 1, j * 2 - 1, (m - j) * 2 })); // top, left, right
                minT = max(0, min({ n - i, j * 2 - 1, (m - j) * 2 })); // bottom, left, right
            }

            minT = 0 - minT;

            int triSum = 0;

            int minX, maxX; minX = maxX = j - 1;

            //cout << "\n\n Up";
            //maxT = -1;
            //bool lineEven = !&even;
            for (int x = 0; x <= maxT; ++x) {
                int line = 0;

                int rrow = i - x - 1;
                vector<Cell>& row = rows[rrow];
                for (Cell& cell : row) {
                    if (minX <= cell.column) {
                        if (cell.column <= maxX) {
                            line += cell.value;
                        }
                        else {
                            break; // over limit, no more left
                        }
                    }
                }
                /*auto it = lower_bound(rows.begin(), rows.end(),
                    [&i, &rrow](const pair<int, vector<Cell>>& element) { return element.first == rrow; });
                if (it != rows.end()) {
                    /*for (Cell& cell : it->second) {
                        if (minX <= cell.column) {
                            if (cell.column <= maxX) {
                                line += cell.value;
                            }
                            else {
                                break; // over limit, no more left
                            }
                        }
                    }
                }*/
                //cout << "\nline " << line << " at triangle part " << x << ", Realrow: " << rrow << " and min/max X: " << minX << "/" << maxX;
                triSum += line;
                if (triSum > maxtri) {
                    maxtri = triSum;
                    cout << "\n !!!!!!!!!!!!!!!!!!!!!New maxtri " << maxtri << " at " << i << " " << j << " with height " << x << " and min/max " << minT << "/" << maxT;
                }

                if (!(rrow & 1)) { // is even
                    minX -= 1;
                }
                else {
                    maxX += 1;
                }
                //if (x == 0) {
                //    triSum = line;
                //    minX, maxX; minX = maxX = j - 1;
                //}
            }
            //cout << "\n-- TRIDONE";
            /*for (vector<int>::reverse_iterator it = upLines.rbegin(); it != upLines.rend(); ++it) {
                triSum -= *it;
                if (triSum > maxtri) {
                    maxtri = triSum;
                    //cout << "\n! New maxtri " << maxtri << " at " << i << " " << j;
                }
            }*/
            // 
            //
            // 
            //cout << "\n\n Down";
            //
            //
            //
            triSum = 0;
            minX = maxX = j - 1;
            for (int x = 0; x >= minT; --x) {
                int line = 0;

                int rrow = i - x - 1;
                vector<Cell>& row = rows[rrow];
                for (Cell& cell : row) {
                    if (minX <= cell.column) {
                        if (cell.column <= maxX) {
                            line += cell.value;
                        }
                        else {
                            break; // over limit, no more left
                        }
                    }
                }
                //cout << "\nline " << line << " at triangle part " << x;
                triSum += line;
                if (triSum > maxtri) {
                    maxtri = triSum;
                    //cout << "\n dNew maxtri " << maxtri << " at " << i << " " << j;
                }

                if (!(rrow & 1)) { // is even
                    minX -= 1;
                }
                else {
                    maxX += 1;
                }
                //if (x == 0) {
                //    triSum = line;
                //    minX, maxX; minX = maxX = j - 1;
                //}
            }
            /*for (int x = 0; x >= minT; --x) {
                int line = 0;
                int rrow = i - x - 1;
                bool lineEven = (rrow % 2 == 0);
                //cout << "\nRow : " << rrow;
                //cout << "\nXrange : " << minX << " - " << maxX;
                auto it = find_if(rows.begin(), rows.end(),
                    [&i,&rrow](const pair<int, vector<Cell>>& element) { return element.first == rrow; });
                if (it != rows.end()) {
                    for (Cell& cell : it->second) {
                        if (minX <= cell.column) {
                            if (cell.column <= maxX) {
                                line += cell.value;
                            }
                            else {
                                break; // over limit, no more left
                            }
                        }
                    }
                }
                //cout << "\nline " << line << " at triangle part " << x;
                triSum += line;
                downLines.push_back(line);

                if (lineEven) {
                    minX -= 1;
                }
                else {
                    maxX += 1;
                }
            }
            //cout << "\n-- TRIDONE";*/
        }
        //cout << "\n " << maxtri;
        even = !even;
    }

    //cout << debugitercount;

    //cout << "\n-- THE END --\nElapsed (ms)=" << since(start).count() << " , #2: " << since(start2).count() << endl;
    //cout << "\n\nRowsize: " << rows.size() << " \nTotalscore: " << totalscore << "\nMaxtri: " << maxtri << "\n\n";
    answer = totalscore + maxtri;
    cout << answer << endl;// << "\n";
}

Test details

Test 1

Group: 1, 2

Verdict:

input
5 6 13
1 1 K
5 1 K
2 2 H
4 2 H
...
view save

correct output
-16
view save

user output
(empty)

Error:
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 2

Group: 1, 2

Verdict:

input
5 6 7
1 5 K
4 6 K
2 4 H
2 5 H
...
view save

correct output
0
view save

user output
(empty)

Error:
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 3

Group: 1, 2

Verdict:

input
5 6 7
5 5 K
2 6 K
2 4 H
2 5 H
...
view save

correct output
0
view save

user output
(empty)

Error:
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 4

Group: 1, 2

Verdict:

input
10 10 51
3 3 H
6 3 H
9 5 H
5 10 H
...
view save

correct output
50
view save

user output
(empty)

Error:
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 5

Group: 1, 2

Verdict:

input
10 10 52
3 5 H
3 1 H
9 6 H
2 8 H
...
view save

correct output
40
view save

user output
(empty)

Error:
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 6

Group: 1, 2

Verdict:

input
10 10 60
6 10 H
2 8 H
5 8 H
8 10 H
...
view save

correct output
-15
view save

user output
(empty)

Error:
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 7

Group: 1, 2

Verdict:

input
10 10 60
4 7 H
7 4 H
4 10 H
3 6 H
...
view save

correct output
60
view save

user output
(empty)

Error:
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 8

Group: 1, 2

Verdict:

input
10 10 40
9 9 H
5 10 H
5 6 H
4 9 H
...
view save

correct output
2
view save

user output
(empty)

Error:
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 9

Group: 1, 2

Verdict:

input
1 1 0
view save

correct output
0
view save

user output
(empty)

Error:
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 10

Group: 1, 2

Verdict:

input
1 1 1
1 1 K
view save

correct output
0
view save

user output
(empty)

Error:
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 11

Group: 1, 2

Verdict:

input
1 1 1
1 1 H
view save

correct output
0
view save

user output
(empty)

Error:
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 12

Group: 1, 2

Verdict:

input
10 5 32
10 3 H
4 4 H
3 3 H
5 4 H
...
view save

correct output
20
view save

user output
(empty)

Error:
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 13

Group: 1, 2

Verdict:

input
5 10 32
5 9 H
2 4 H
2 9 H
2 5 H
...
view save

correct output
28
view save

user output
(empty)

Error:
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 14

Group: 1, 2

Verdict:

input
10 10 100
2 9 H
5 4 H
5 9 K
6 1 K
...
view save

correct output
-439
view save

user output
(empty)

Error:
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 15

Group: 1, 2

Verdict:

input
10 10 100
8 9 H
5 10 H
5 4 H
3 9 H
...
view save

correct output
88
view save

user output
(empty)

Error:
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 16

Group: 2

Verdict:

input
500 500 125000
125 261 K
84 78 K
11 200 K
481 246 K
...
view save

correct output
-624270
view save

user output
(empty)

Error:
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 17

Group: 2

Verdict:

input
500 500 125100
16 61 H
37 62 H
459 125 H
318 476 H
...
view save

correct output
124020
view save

user output
(empty)

Error:
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 18

Group: 2

Verdict:

input
500 500 249999
22 214 H
356 145 H
341 29 H
393 262 H
...
view save

correct output
249999
view save

user output
(empty)

Error:
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 19

Group: 2

Verdict:

input
500 500 32000
30 81 H
315 34 H
78 112 H
367 166 H
...
view save

correct output
10126
view save

user output
(empty)

Error:
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 20

Group: 2

Verdict:

input
500 500 126745
164 390 H
126 331 H
164 126 H
55 92 H
...
view save

correct output
-104692
view save

user output
(empty)

Error:
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 21

Group: 2

Verdict:

input
500 500 71200
106 191 H
314 189 H
482 485 H
344 401 H
...
view save

correct output
-335853
view save

user output
(empty)

Error:
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 22

Group: 2

Verdict:

input
500 500 67772
421 277 H
428 470 H
169 142 H
256 345 H
...
view save

correct output
-208567
view save

user output
(empty)

Error:
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 23

Group: 2

Verdict:

input
500 500 27434
366 481 H
38 22 H
126 107 H
135 169 H
...
view save

correct output
-57100
view save

user output
(empty)

Error:
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 24

Group: 2

Verdict:

input
500 500 93982
183 13 H
463 230 H
264 351 H
399 290 H
...
view save

correct output
-52800
view save

user output
(empty)

Error:
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Tasks

A Lumimyrsky-B Monistus-C Laskettelukeskus-D Uolevin kalansaalis-E Käännöt-F Säähavainnot-

Submissions (Username*)

2023-11-11 14:45:05 1002023-11-11 14:44:14 02023-11-11 13:58:26 372023-11-02 22:00:15 372023-11-02 21:59:38 02023-11-02 16:51:07 02023-11-02 16:50:47 02023-11-02 16:37:44 02023-11-02 16:28:16 02023-11-01 18:08:55 02023-11-01 17:39:11 02023-11-01 17:38:44 02023-11-01 17:28:20 02023-11-01 17:27:39 02023-11-01 17:25:29 02023-11-01 17:25:11 02023-11-01 17:24:34 0