Submission #949588

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
949588	2024-03-19T11:39:20 Z	GrindMachine	Sailing Race (CEOI12_race)	C++17	40 / 100	291 ms	5820 KB

race

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*



*/

const int MOD = 1e9 + 7;
const int N = 500 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

vector<int> adj[N];

void solve(int test_case)
{
    int n,k; cin >> n >> k;
    rep(u,n){
        while(true){
            int v; cin >> v;
            v--;
            if(v == -1) break;
            assert(u != v);
            adj[u].pb(v);
        }
    }

    vector<array<int,3>> order;
    rep(l,n){
        rep(r,n){
            int len = 0;
            if(l <= r){
                len = r-l+1;
            }
            else{
                len = n-l+r+1;
            }

            order.pb({len,l,r});
        }
    }

    sort(all(order));

    int dp[n][n][2];
    memset(dp,0,sizeof dp);

    auto in_range = [&](int i, int l, int r){
        if(l <= r){
            return i >= l and i <= r;
        }
        else{
            return i >= l or i <= r;
        }
    };

    for(auto [len,l,r] : order){
        if(l == r){
            rep(j,2){
                int u = 0;
                if(!j) u = l-1;
                else u = r+1;
                u = (u%n+n)%n;

                trav(v,adj[u]){
                    if(v == l){
                        dp[l][r][j] = 1;
                    }
                }
            }
        }
        else{
            rep(j,2){
                int u = 0;
                if(!j) u = l-1;
                else u = r+1;
                u = (u%n+n)%n;

                trav(v,adj[u]){
                    if(!in_range(v,l,r)) conts;

                    int val = 0;
                    if(v != l){
                        amax(val,dp[l][(v-1+n)%n][1]);
                    }
                    if(v != r){
                        amax(val,dp[(v+1)%n][r][0]);
                    }

                    val++;
                    amax(dp[l][r][j],val);
                }
            }
        }
    }

    pii ans = {0,0};

    rep(u,n){
        trav(v,adj[u]){
            int val = 0;
            if((u+1)%n != v){
                amax(val,dp[(u+1)%n][(v-1+n)%n][1]);
            }
            if((v+1)%n != u){
                amax(val,dp[(v+1)%n][(u-1+n)%n][0]);
            }

            val++;
            pii px = {val,u};
            amax(ans,px);
        }
    }

    ans.ss++;
    cout << ans.ff << endl << ans.ss << endl;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Subtask #1

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Incorrect	0 ms	348 KB	Output isn't correct
3	Incorrect	1 ms	348 KB	Output isn't correct
4	Incorrect	1 ms	348 KB	Output isn't correct
5	Correct	1 ms	348 KB	Output is correct
6	Incorrect	1 ms	348 KB	Output isn't correct
7	Correct	3 ms	600 KB	Output is correct
8	Incorrect	2 ms	604 KB	Output isn't correct
9	Correct	5 ms	604 KB	Output is correct
10	Correct	13 ms	796 KB	Output is correct
11	Correct	7 ms	796 KB	Output is correct
12	Incorrect	21 ms	1368 KB	Output isn't correct
13	Incorrect	41 ms	2260 KB	Output isn't correct
14	Correct	71 ms	4564 KB	Output is correct
15	Incorrect	196 ms	5580 KB	Output isn't correct
16	Incorrect	244 ms	5700 KB	Output isn't correct
17	Incorrect	192 ms	5572 KB	Output isn't correct
18	Correct	97 ms	5412 KB	Output is correct
19	Incorrect	287 ms	5820 KB	Output isn't correct
20	Incorrect	291 ms	5760 KB	Output isn't correct