Submission #1090391

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1090391	2024-09-18T10:31:32 Z	vjudge1	Sailing Race (CEOI12_race)	C++14	75 / 100	906 ms	6652 KB

race

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, k, i, j, l, r, d, t, u;
    cin >> n >> k;
    vector<vector<int> > le(n), ri(n), dle(n), dri(n), pr(n), ne(n);
    vector<vector<bool> > w(n);
    for (i = 0; i < n; i++)
    {
        le[i].resize(n);
        ri[i].resize(n);
        dle[i].resize(n);
        dri[i].resize(n);
        w[i].resize(n);
        pr[i].resize(n);
        ne[i].resize(n);
        for (j = 0; j < n; j++)
            w[i][j] = 0;
        while (1)
        {
            cin >> d;
            if (!d)
                break;
            w[i][d - 1] = 1;
        }
    }
    for (i = 0; i < n; i++)
    {
        for (l = 0; l < n; l++)
        {
            r = (l + i) % n;
            le[l][r] = ri[l][r] = 0;
            if (i)
                dle[l][r] = dri[l][r] = 0;
            else
                dle[l][r] = dri[l][r] = -1;
            if (w[l][r])
                dle[l][r] = 1;
            if (w[r][l])
                dri[l][r] = 1;
            for (j = 1; j < i; j++)
            {
                d = (l + j) % n;
                t = max(ri[l][d], le[d][r]) + 1;
                if (w[l][d])
                {
                    le[l][r] = max(le[l][r], t);
                    dle[l][r] = max(dle[l][r], dle[d][r] + 1);
                }
                if (w[r][d])
                {
                    ri[l][r] = max(ri[l][r], t);
                    dri[l][r] = max(dri[l][r], dri[l][d] + 1);
                }
            }
        }
    }
    t = u = 0;
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            if (!w[i][j])
                continue;
            d = max(ri[i][j], le[j][i]) + 1;
            if (d > t)
            {
                t = d;
                u = i;
            }
        }
    }
    if (k)
    {
        for (i = 0; i < n; i++)
        {
            for (j = 0; j < n; j++)
                pr[i][j] = ne[i][j] = -1;
            for (j = n - 1; j >= 0; j--)
            {
                if (w[j][i])
                {
                    pr[i][0] = j;
                    break;
                }
            }
            for (j = 1; j < n; j++)
            {
                if (w[j - 1][i])
                    pr[i][j] = j - 1;
                else
                    pr[i][j] = pr[i][j - 1];
            }
            for (j = 0; j < n; j++)
            {
                if (w[j][i])
                {
                    ne[i][n - 1] = j;
                    break;
                }
            }
            for (j = n - 2; j >= 0; j--)
            {
                if (w[j + 1][i])
                    ne[i][j] = j + 1;
                else
                    ne[i][j] = ne[i][j + 1];
            }
        }
        for (j = 0; j < n; j++)
        {
            if (pr[j][0] == -1)
                continue;
            for (l = 0; l < n; l++)
            {
                if (l == j)
                    continue;
                i = pr[j][l];
                if (i != l && (i + n - j) % n + (l + n - i) % n == (l + n - j) % n)
                {
                    for (r = j + 1;; r++)
                    {
                        if (r >= n)
                            r -= n;
                        if (r == i)
                            break;
                        if (!w[l][r])
                            continue;
                        d = max(ri[j][r], le[r][i]) + dri[l][j] + 2;
                        if (d > t)
                        {
                            t = d;
                            u = i;
                        }
                    }
                }
                i = ne[j][l];
                if (i != l && (i + n - l) % n + (j + n - i) % n == (j + n - l) % n)
                {
                    i = ne[j][l];
                    for (r = i + 1;; r++)
                    {
                        if (r >= n)
                            r -= n;
                        if (r == j)
                            break;
                        if (!w[l][r])
                            continue;
                        d = max(ri[i][r], le[r][j]) + dle[j][l] + 2;
                        if (d > t)
                        {
                            t = d;
                            u = i;
                        }
                    }
                }
            }
        }
    }
    cout << t << "\n" << u + 1;
    return 0;
}

Subtask #1

75.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	456 KB	Output is correct
4	Incorrect	1 ms	348 KB	Output isn't correct
5	Correct	1 ms	344 KB	Output is correct
6	Correct	2 ms	344 KB	Output is correct
7	Correct	3 ms	348 KB	Output is correct
8	Correct	4 ms	604 KB	Output is correct
9	Correct	6 ms	680 KB	Output is correct
10	Correct	4 ms	604 KB	Output is correct
11	Correct	8 ms	604 KB	Output is correct
12	Incorrect	53 ms	1456 KB	Output isn't correct
13	Incorrect	126 ms	2668 KB	Output isn't correct
14	Correct	141 ms	4188 KB	Output is correct
15	Correct	662 ms	6592 KB	Output is correct
16	Correct	768 ms	6620 KB	Output is correct
17	Incorrect	683 ms	6592 KB	Output isn't correct
18	Correct	242 ms	6492 KB	Output is correct
19	Correct	882 ms	6644 KB	Output is correct
20	Incorrect	906 ms	6652 KB	Output isn't correct