Submission #1035982

# Submission time Handle Problem Language Result Execution time Memory
1035982 2024-07-27T00:13:31 Z Requiem Sailing Race (CEOI12_race) C++17
80 / 100
3000 ms 19036 KB
#include<bits/stdc++.h>
//#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define inf 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "sailrace"
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
const int MAXN = 3e5 + 9;
string str;
int n, k;
vector<int> g[MAXN], backEdge[MAXN];

void extract(int curId){
     int num = 0, cnt = 0;
//     cout << str << endl;
     str = str + ' ';
     for(int i = 0; i < str.length(); i++){
         if (str[i] != ' ') {
             num = num * 10 + (str[i] - '0');
//             cout << num << ' ' << str[i] - '0' << endl;
         }
         else {
             if (num != 0) {
                 g[curId].pb(num);
                 backEdge[num].pb(curId);
                 cnt++;
//                 cout << curId << ' ' << num << endl;
             }
             else break;

             num = 0;

         }
     }
     assert(cnt <= 500);
}

namespace subtask1{
    bool check(){
         return k == 0;
    }

    int dp[2][501][501], memo[2][501][501], backward = 0;
    int bestI = 0, res = 0;

    int goBack(int id){
        return (id - backward <= 0) ? id - backward + n : (id - backward);
    }

    int goUp(int id){
        return (id + backward) - ((id + backward > n) ? (n) : 0);
    }



    int memorization(int state, int Larc, int Rarc){

        if (dp[state][Larc][Rarc] != -1) return dp[state][Larc][Rarc];
        if (memo[state][goUp(Larc)][goUp(Rarc)] != -1) return memo[state][goUp(Larc)][goUp(Rarc)];
        if (Larc >= Rarc) return 0;

        dp[state][Larc][Rarc] = 0;
        int cur = goUp((state) ? Rarc : Larc);

        if (state == 0){
            for(auto v: g[cur]){
                int curV = goBack(v);
//                cout << cur << ' ' << curV << ' ' << v << endl;
//                cout << cur << ' ' << v << endl;
                if (curV > Larc and curV <= Rarc) {
                    maximize(dp[0][Larc][Rarc], 1 + max(memorization(0, curV, Rarc), memorization(1, Larc + 1, curV)));
                }
            }
        }
        else{
            for(auto v: g[cur]){
                int curV = goBack(v);
                if (curV >= Larc and curV < Rarc) {
                    maximize(dp[1][Larc][Rarc], 1 + max(memorization(0, curV, Rarc - 1), memorization(1, Larc, curV)));
                }
            }
        }
        memo[state][goUp(Larc)][goUp(Rarc)] = dp[state][Larc][Rarc];
//        cout << "MEMO: " << state << ' ' << goUp(Larc) << ' ' << goUp(Rarc) << ' ' << memo[state][goUp(Larc)][goUp(Rarc)] << endl;

//        cout << "DP: " << state << ' ' << Larc << ' ' << Rarc << ' ' << dp[state][Larc][Rarc] << endl;
        return dp[state][Larc][Rarc];
    }
    int modify(int x){
        return (x > n) ? (x - n) : x;
    }

    bool onRange(int l, int r, int x){
         return x >= l and x <= r;
    }
    bool onArc(int l, int r, int x){
        l = modify(l);
        r = modify(r);
        if (l > r) r += n;
        return onRange(l, r, x) | onRange(l, r, x + n);
    }
    int dist(int i, int j){
        i = modify(i);
        j = modify(j);
        return min(abs(i - j), abs(i + n - j));
    }
    bool RightArc(int l, int r, int x){
        if (l > r) {
            r += n;
        }
        return dist(r, x) < dist(l, x);
    }
    void solve(int print = 1){
        memset(memo, -1, sizeof(memo));
        for(int i = 1;i <= n; i++){
            memset(dp, -1, sizeof(dp));
            backward = i - 1;
//            cout << i << endl;
            int mx = memorization(0, 1, n);
            if (maximize(res, mx)){
                bestI = i;
            }
//            cout << endl;
        }
        if (print == 1) cout << res << endl;
        if (print == 1) cout << bestI << endl;

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                for(int state = 0; state < 2; state++){
                    if (memo[state][i][j] == -1) memo[state][i][j] = 0;
                }
            }
        }

        for(int i = 1; i <= n; i++){
            for(auto v: g[i]){
                maximize(memo[0][i][v], 1);
                maximize(memo[1][v][i], 1);
            }
        }

        for(int len = 1; len <= n; len++){
            for(int i = 1, j = i + len - 1; i <= n; i++){
                if (j > n) j -= n;
                for(int state = 0; state < 2; state++){
                    int cur = (state == 0) ? i : j;
                    for(auto v: backEdge[cur]){
                        if (!onArc(i, j, v)) {
                            if (RightArc(i, j, v)) maximize(memo[1][i][v], memo[state][i][j] + 1);
                            else maximize(memo[0][v][j], memo[state][i][j] + 1);
//                            if (i == 3 and j == 5) cout << cur << ' ' << v << ' ' << memo[0][2][5] << endl;

                        }
                    }
                }
            }
        }
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                for(int state = 0; state < 2; state++){
//                    cout << state << ' ' << i << ' ' << j << ' ' << memo[state][i][j] << endl;
                }
            }
        }

    }
}

namespace subtask2{
    bool check(){
         return k == 1;
    }

    int backward = 0;

    int goVirtual(int id){
        return (id - backward <= 0) ? id - backward + n : (id - backward);
    }

    int goOrigin(int id){
        return (id + backward) - ((id + backward > n) ? (n) : 0);
    }

    int dpRight[505], dpLeft[505];

    int solveRight(int cur, int intersect){
        if (dpRight[cur] != -1) return dpRight[cur];
        int u = goOrigin(cur);

        dpRight[cur] = 0;
        for(auto v: g[u]){
            int curV = goVirtual(v);
            if (curV < cur and curV > 1){
                maximize(dpRight[cur], solveRight(curV, intersect) + 1);
            }
            else if (curV > intersect and cur != intersect) {
                maximize(dpRight[cur], subtask1::memo[1][goOrigin(intersect + 1)][goOrigin(curV)] + 1);
                maximize(dpRight[cur], subtask1::memo[0][goOrigin(curV)][goOrigin(n)] + 1);
            }
        }
//        cout << "CUR: " << u << ' ' << cur << ' ' << dpRight[cur] << endl;

        return dpRight[cur];
    }

    int solveLeft(int cur, int intersect){
        if (dpLeft[cur] != -1) return dpLeft[cur];
        int u = goOrigin(cur);

        dpLeft[cur] = 0;
        for(auto v: g[u]){
            int curV = goVirtual(v);
            if (curV > cur){
                maximize(dpLeft[cur], solveLeft(curV, intersect) + 1);
            }
            else if (curV > 1 and curV < intersect and cur != intersect) {
                maximize(dpLeft[cur], subtask1::memo[0][goOrigin(curV)][goOrigin(intersect - 1)] + 1);
                maximize(dpLeft[cur], subtask1::memo[1][goOrigin(2)][goOrigin(curV)] + 1);
            }
        }
//        cout << "LEFTCUR: " << intersect << ' ' << u << ' ' << cur << ' ' << dpLeft[cur] << endl;

        return dpLeft[cur];
    }

    void solve(){
         subtask1::solve(0);
         int res = subtask1::res, bestI = subtask1::bestI;
         for(int i = 1; i <= n; i++){
             backward = i - 1;
             for(auto v: g[i]){
                 for(int j = 1; j <= goVirtual(v); j++){
                     dpRight[j] = -1;
                 }
                 for(int j = goVirtual(v); j <= n; j++){
                     dpLeft[j] = -1;
                 }
//                 cout << 1 << ' ' << goVirtual(v) << endl;
                 int m1 = 0, m2 = 0;
                 m1 = solveRight(goVirtual(v), goVirtual(v)) + 1;
                 m2 = solveLeft(goVirtual(v), goVirtual(v)) + 1;

                 if (maximize(res, m1) or maximize(res, m2)){
                     bestI = i;
                 }

             }
         }
         cout << res << endl;
         cout << bestI << endl;
    }


}
main()
{
    fast;
    if (fopen(TASKNAME".inp","r")){
        freopen(TASKNAME".inp","r",stdin);
        freopen(TASKNAME".out","w",stdout);
    }
    cin >> n >> k;
    cin.ignore();
    for(int i = 1; i <= n; i++){
        getline(cin, str);
        extract(i);
    }

    if (subtask1::check()) return subtask1::solve(), 0;
    if (subtask2::check()) return subtask2::solve(), 0;


}
/**
Warning:
- MLE / TLE?
- Gioi han mang?
- Gia tri max phai luon gan cho -INF
- long long co can thiet khong?
- tran mang.
- code can than hon
- Nho sinh test de tranh RTE / TLE

--> Coi lai truoc khi nop
**/

Compilation message

race.cpp: In function 'void extract(int)':
race.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |      for(int i = 0; i < str.length(); i++){
      |                     ~~^~~~~~~~~~~~~~
race.cpp: At global scope:
race.cpp:269:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  269 | main()
      | ^~~~
race.cpp: In function 'int main()':
race.cpp:273:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  273 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:274:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  274 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 8 ms 18268 KB Output is correct
2 Correct 8 ms 18260 KB Output is correct
3 Correct 9 ms 18400 KB Output is correct
4 Correct 10 ms 18264 KB Output is correct
5 Correct 11 ms 18268 KB Output is correct
6 Correct 15 ms 18288 KB Output is correct
7 Correct 16 ms 18520 KB Output is correct
8 Correct 16 ms 18460 KB Output is correct
9 Correct 17 ms 18552 KB Output is correct
10 Correct 26 ms 18524 KB Output is correct
11 Correct 20 ms 18524 KB Output is correct
12 Correct 178 ms 18524 KB Output is correct
13 Correct 255 ms 18524 KB Output is correct
14 Correct 103 ms 18520 KB Output is correct
15 Incorrect 2588 ms 18776 KB Output isn't correct
16 Execution timed out 3019 ms 19036 KB Time limit exceeded
17 Correct 2618 ms 18912 KB Output is correct
18 Correct 141 ms 18520 KB Output is correct
19 Execution timed out 3074 ms 19036 KB Time limit exceeded
20 Execution timed out 3030 ms 19032 KB Time limit exceeded