— 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:Tipu
Submission time:2023-11-04 17:32:36 +0200
Language:C++ (C++11)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2details
#20.02 s1, 2details
#30.02 s1, 2details
#4ACCEPTED0.02 s1, 2details
#5ACCEPTED0.02 s1, 2details
#60.01 s1, 2details
#70.02 s1, 2details
#8ACCEPTED0.02 s1, 2details
#9ACCEPTED0.02 s1, 2details
#10ACCEPTED0.02 s1, 2details
#11ACCEPTED0.02 s1, 2details
#120.02 s1, 2details
#130.01 s1, 2details
#14ACCEPTED0.02 s1, 2details
#15ACCEPTED0.01 s1, 2details
#16ACCEPTED0.55 s2details
#170.16 s2details
#180.22 s2details
#190.11 s2details
#20ACCEPTED0.23 s2details
#21ACCEPTED0.43 s2details
#22ACCEPTED0.30 s2details
#230.12 s2details
#240.16 s2details

Code

#include<iostream>
#include <deque>
#include <vector>
#include <algorithm>
#include <cmath>
#include <unordered_map>
using namespace std;
typedef long long ll;


struct Hex {       
  public:            
    int l = 0;   
    int r = 0;
    int x = 0;
};

const int SIZE = 501;

int n, m, k;
int v[SIZE][SIZE];
Hex d[SIZE][SIZE];
unordered_map<int, pair<bool, bool>> sm[SIZE][SIZE];

int count_l_colum(int i, int j, int l){
    bool add = (i % 2 == 0);
    if(i-l < 0 || i >= n + 1 || j - int(ceil((l-add)/2.0)) < 0 || j >= m + 1){
        return 1e6;
    }
    return (d[i][j].l - d[i-l][j - int(ceil((l-add)/2.0))].l);
} 

int count_r_colum(int i, int j, int l){
    bool add = (i % 2 == 0);
    if(i-l < 0 || i >= n + 1 || j < 0 || j + int((l+add)/2.0) >= m + 1){
        return 1e6;
    }
    return (d[i][j].r - d[i-l][j + int((l+add)/2.0)].r);
} 

int count_x_colum(int i, int j, int l){
    if(i < 0 || i >= n + 1 || j-l < 0 || j >= m + 1){
        return 1e6;
    }
    return (d[i][j].x - d[i][j-l].x);
} 
int scan(int p){

    pair<short, short> a, b, c;

    int safe_sum = 0;
    for (int i = n; i >= 1; i--) {
        for (int j = 1; j <= m; j++)
        {
            a = {i, j};
            b = {i, j};
            int s = count_x_colum(i, j, 1);
            int l = 1;
            bool up = true;
            int safety = 0;
            while(safety < 1e6){
                safety++;
                auto it = sm[a.first][a.second].find(l);

                if(l == 1) up = true;

                //tsekataan onko muistissa
                if(it != sm[a.first][a.second].end()){
                    if((up && it->second.first) || (!up && it->second.second)){
                        break;
                    }
                    else{
                        if(up) it->second.first = true;
                        else it->second.second = true;
                    }
                //lisätään muistikohta
                } else{
                    if (up) sm[a.first][a.second].insert({l, {true, false}});
                    else sm[a.first][a.second].insert({l, {false, true}});
                }


                bool add = (b.first % 2 == 0);
                if(l == 1){

                    int su1 = count_l_colum(b.first, b.second + 1, l + 1);
                    int su2 = count_x_colum(b.first + 1, b.second + add, l + 1);
                    int su3 = count_r_colum(a.first, a.second - 1, l + 1);

                    int su = min({su1, su2, su3});

                    int sd1 = count_l_colum(b.first + 1, b.second + (add - 1), l + 1);
                    int sd2 = count_x_colum(b.first - l, b.second + int((l+add)/2.0), l + 1);
                    int sd3 = count_r_colum(b.first + 1, b.second + add, l + 1);

                    int sd = min({sd1, sd2, sd3});

                    if(su <= sd && su < 0){
                        up = true;
                        l += 1;
                        if(su1 <= su2 && su1 <= su3){
                            s+=su1;
                            b = {b.first, b.second + 1};
                            continue;
                        }
                        if(su2 <= su3 && su2 <= su1){
                            s += su2;
                            b = {b.first + 1, b.second + add};
                            a = {a.first + 1, a.second + (add - 1)};
                            continue;
                        }
                        if(su3 <= su1 && su3 <= su2){
                            s += su3;
                            a = {a.first, a.second - 1};
                            continue;
                        }
                    }
                    else if (sd < 0){
                        up = false;
                        l += 1;
                        if(sd1 <= sd2 && sd1 <= sd3){
                            s+=sd1;
                            a = {a.first, a.second - 1};
                            b = {b.first + 1, b.second + (add - 1)};
                            continue;
                        }
                        if(sd2 <= sd3 && sd2 <= sd1){
                            s += sd2;
                            a = {a.first - 1, a.second + (add - 1)};
                            continue;
                        }
                        if(sd3 <= sd1 && sd3 <= sd2){
                            s += sd3;
                            b = {b.first + 1, b.second + add};
                            continue;
                        }
                    }
                    else{
                        break;
                    }
                }
                if(l != 0){
                    if(up){
                        int su1 = count_l_colum(b.first, b.second + 1, l + 1);
                        int su2 = count_x_colum(b.first + 1, b.second + add, l + 1);
                        int su3 = count_r_colum(a.first, a.second - 1, l + 1);

                        int su = min({su1, su2, su3});

                        int ru1 = -1 * count_l_colum(b.first, b.second, l);
                        int ru2 = -1 * count_x_colum(b.first, b.second, l);
                        int ru3 = -1 * count_r_colum(a.first, a.second , l);

                        int ru = min({su1, su2, su3});

                        if(su <= ru && su < 0){
                            l += 1;
                            if(su1 <= su2 && su1 <= su3){
                                s+=su1;
                                b = {b.first, b.second + 1};
                                continue;
                            }
                            if(su2 <= su3 && su2 <= su1){
                                s += su2;
                                b = {b.first + 1, b.second + add};
                                a = {a.first + 1, a.second + (add - 1)};
                                continue;
                            }
                            if(su3 <= su1 && su3 <= su2){
                                s += su3;
                                a = {a.first, a.second - 1};
                                continue;
                            }
                        }
                        else if(ru < 0){
                            l -= 1;
                            if(ru1 <= ru2 && ru1 <= ru3){
                                s += ru1;
                                b = {b.first, b.second - 1};
                                continue;
                            }
                            if(ru2 <= ru3 && ru2 <= ru1){
                                s += ru2;
                                b = {b.first - 1, b.second + (add - 1)};
                                a = {a.first - 1, a.second + add};
                                continue;
                            }
                            if(ru3 <= ru1 && ru3 <= ru2){
                                s += ru3;
                                a = {a.first, a.second + 1};
                                continue;
                            }
                        }
                        else{
                            break;
                        }
                    }
                    else{
                        int sd1 = count_l_colum(b.first + 1, b.second + (add - 1), l + 1);
                        int sd2 = count_x_colum(b.first - l, b.second + int((l+add)/2.0), l + 1);
                        int sd3 = count_r_colum(b.first + 1, b.second + add, l + 1);

                        int sd = min({sd1, sd2, sd3});

                        int rd1 = -1 * count_l_colum(b.first, b.second, l);
                        int rd2 = -1 * count_x_colum(a.first, a.second + l - 1, l);
                        int rd3 = -1 * count_r_colum(b.first, b.second, l);

                        int rd = min({sd1, sd2, sd3});

                        if(sd <= rd && sd < 0){
                            l += 1;
                            if(sd1 <= sd2 && sd1 <= sd3){
                                s+=sd1;
                                a = {a.first, a.second - 1};
                                b = {b.first + 1, b.second + (add - 1)};
                                continue;
                            }
                            if(sd2 <= sd3 && sd2 <= sd1){
                                s += sd2;
                                a = {a.first - 1, b.second - int(ceil((l-add)/2.0))};
                                continue;
                            }
                            if(sd3 <= sd1 && sd3 <= sd2){
                                s += sd3;
                                b = {b.first + 1, b.second + add};
                                continue;
                            }
                        }
                        else if(rd < 0){
                            l -= 1;
                            if(rd1 <= rd2 && rd1 <= rd3){
                                s+=rd1;
                                a = {a.first, a.second + 1};
                                b = {b.first - 1, b.second + add};
                                continue;
                            }
                            if(rd2 <= rd3 && rd2 <= rd1){
                                s += rd2;
                                a = {a.first + 1, b.second - int((l-add)/2.0)};
                                continue;
                            }
                            if(rd3 <= rd1 && rd3 <= rd2){
                                s += sd3;
                                b = {b.first - 1, b.second + (add - 1)};
                                continue;
                            }
                        }
                        else{
                            break;
                        }
                    }
                }
            }
            p = min(s, p);
            // cout << "( " << i << ";" << j << ") s:"  << s << " p:" << p << " safety: " << safety << endl; 
            safe_sum += safety;
        }    
    }     
    // cout << "ss: " << safe_sum << endl;
    return p;   
}


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



    cin >> n >> m >> k;

    int a, b;
    char c;
    for (int i = 0; i < k; i++) {
        cin >> a >> b >> c;
        if(c == 'H'){
            v[a][b] = 1;
        }else{
            v[a][b] = -10;
        }
    }
    int os = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            bool add = 0;
            if(i % 2 == 0){
                add = 1;
            }
            os += v[i][j];
            d[i][j].l = v[i][j] + d[i-1][j-1+add].l;
            d[i][j].r = v[i][j] + d[i-1][j+add].r;
            d[i][j].x = v[i][j] + d[i][j-1].x;
        }
    }

    // for (int i = 1; i <= n; i++) {
    //     for (int j = 1; j <= m; j++) {
    //         cout << "(" << d[i][j].l << " ; " << d[i][j].r << " ; " << d[i][j].x << ")  " ;
    //     }
    //     cout << "\n";
    // }

    int p = 1e6;
    p = scan(p);

    // cout << p << endl;
    // cout << os << endl;
    
    cout << os - p;
}

Test details

Test 1

Group: 1, 2

Verdict: ACCEPTED

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
-16
view save

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
-5
view save

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
-5
view save

Test 4

Group: 1, 2

Verdict: ACCEPTED

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
50
view save

Test 5

Group: 1, 2

Verdict: ACCEPTED

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
40
view save

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
-21
view save

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
64
view save

Test 8

Group: 1, 2

Verdict: ACCEPTED

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
2
view save

Test 9

Group: 1, 2

Verdict: ACCEPTED

input
1 1 0
view save

correct output
0
view save

user output
0
view save

Test 10

Group: 1, 2

Verdict: ACCEPTED

input
1 1 1
1 1 K
view save

correct output
0
view save

user output
0
view save

Test 11

Group: 1, 2

Verdict: ACCEPTED

input
1 1 1
1 1 H
view save

correct output
0
view save

user output
0
view save

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
22
view save

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
29
view save

Test 14

Group: 1, 2

Verdict: ACCEPTED

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
-439
view save

Test 15

Group: 1, 2

Verdict: ACCEPTED

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
88
view save

Test 16

Group: 2

Verdict: ACCEPTED

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
-624270
view save

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
124277
view save

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
250496
view save

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
10054
view save

Test 20

Group: 2

Verdict: ACCEPTED

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
-104692
view save

Test 21

Group: 2

Verdict: ACCEPTED

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
-335853
view save

Test 22

Group: 2

Verdict: ACCEPTED

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
-208567
view save

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
-115191
view save

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
-106370
view save

Tasks

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

Submissions (Tipu)

2023-11-14 12:20:52 372023-11-14 12:20:11 2023-11-14 12:18:22 02023-11-14 12:14:49 372023-11-14 12:13:23 372023-11-14 12:13:04 2023-11-14 12:11:25 372023-11-14 12:09:44 02023-11-14 12:08:15 372023-11-13 00:36:29 372023-11-13 00:33:45 372023-11-13 00:32:11 02023-11-13 00:31:31 02023-11-13 00:00:10 02023-11-12 23:59:14 372023-11-12 23:59:01 372023-11-12 23:58:41 372023-11-12 23:58:08 372023-11-12 23:57:56 02023-11-12 23:57:44 02023-11-12 23:57:30 02023-11-12 23:57:19 02023-11-12 23:57:02 372023-11-12 23:56:05 372023-11-12 23:51:34 372023-11-12 23:49:56 372023-11-12 23:32:32 372023-11-12 23:31:50 372023-11-12 23:31:34 372023-11-12 23:31:16 2023-11-12 23:30:59 2023-11-12 23:29:47 02023-11-12 23:29:08 02023-11-12 23:28:55 372023-11-12 23:28:36 372023-11-12 23:28:21 372023-11-12 23:27:32 02023-11-12 23:26:47 02023-11-12 23:26:31 02023-11-12 23:26:23 02023-11-12 23:26:12 2023-11-12 23:24:20 02023-11-12 23:23:57 372023-11-12 23:23:44 02023-11-12 23:23:27 02023-11-12 22:45:08 02023-11-12 22:43:28 02023-11-12 22:43:02 372023-11-12 22:16:25 372023-11-12 22:13:15 372023-11-12 22:12:52 02023-11-12 22:12:28 02023-11-12 22:11:58 372023-11-12 22:09:00 372023-11-12 22:07:22 372023-11-12 22:07:10 02023-11-12 21:47:39 02023-11-12 21:36:51 02023-11-12 21:35:12 372023-11-12 21:23:07 372023-11-12 21:22:42 2023-11-12 21:00:26 372023-11-12 20:59:17 372023-11-12 20:57:09 372023-11-12 20:55:32 372023-11-12 20:55:08 372023-11-12 20:54:55 372023-11-12 20:54:36 372023-11-12 20:54:18 372023-11-12 20:54:06 372023-11-12 20:53:55 372023-11-12 20:53:41 372023-11-12 20:53:28 372023-11-12 20:53:13 372023-11-12 20:52:54 372023-11-12 20:52:17 372023-11-12 20:52:02 372023-11-12 20:51:47 372023-11-12 20:51:32 372023-11-12 20:51:15 372023-11-12 20:50:57 372023-11-12 20:48:46 372023-11-12 20:45:05 372023-11-12 20:44:20 372023-11-12 20:43:56 2023-11-12 20:43:33 372023-11-12 20:43:14 2023-11-12 20:42:50 372023-11-12 20:42:19 372023-11-12 20:19:47 02023-11-12 20:06:18 02023-11-12 20:05:01 02023-11-12 20:04:42 02023-11-12 19:53:06 372023-11-12 19:52:49 02023-11-12 19:39:33 02023-11-05 18:12:04 372023-11-05 18:09:30 02023-11-05 17:29:44 02023-11-04 22:13:17 02023-11-04 22:09:25 02023-11-04 22:09:04 02023-11-04 22:08:21 02023-11-04 22:08:08 02023-11-04 22:07:44 02023-11-04 22:07:24 02023-11-04 22:07:15 02023-11-04 22:07:00 02023-11-04 22:06:45 02023-11-04 22:06:24 02023-11-04 21:23:30 02023-11-04 21:23:05 02023-11-04 21:22:50 02023-11-04 21:19:31 02023-11-04 21:19:13 02023-11-04 21:18:53 02023-11-04 21:12:55 02023-11-04 21:03:14 02023-11-04 18:18:32 02023-11-04 18:18:00 02023-11-04 18:16:37 02023-11-04 18:16:15 02023-11-04 18:15:52 02023-11-04 18:14:24 2023-11-04 18:13:05 2023-11-04 18:05:21 02023-11-04 17:32:36 02023-11-04 17:19:11 02023-10-30 23:57:14 0