oj.uz

Submission #1088811

# Submission time Handle Problem Language Result Execution time Memory
1088811 2024-09-15T06:43:32 Z pokmui9909 Good Game (CCO22_day2problem3) C++17
0 / 25
 0 ms 348 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define x first
#define y second

ll N; string S;
ll D[6005][6005];

vector<pair<ll, ll>> V;

void f(ll i, ll j){
    ll k = j - i + 1;
         if(k >= 2 && S[i] == S[i + 1] && D[i + 2][j]) f(i + 2, j), V.push_back({i, 2});
    else if(k >= 2 && S[j] == S[j - 1] && D[i][j - 2]) f(i, j - 2), V.push_back({i, 2});
    else if(k >= 2 && S[i] == S[j] && D[i + 1][j - 1]) f(i + 1, j - 1), V.push_back({i, 2});

    else if(k >= 3 && S[i] == S[i + 1] && S[i + 1] == S[i + 2] && D[i + 3][j]) f(i + 3, j), V.push_back({i, 3});
    else if(k >= 3 && S[j] == S[j - 1] && S[j - 1] == S[j - 2] && D[i][j - 3]) f(i, j - 3), V.push_back({i, 3});
    else if(k >= 3 && S[i] == S[j - 1] && S[j - 1] == S[j] && D[i + 1][j - 2]) f(i + 1, j - 2), V.push_back({i, 3});
    else if(k >= 3 && S[i] == S[i + 1] && S[i + 1] == S[j] && D[i + 2][j - 1]) f(i + 2, j - 1), V.push_back({i, 3});

    else {
        for(ll t = i; t < j; t++){
            if(D[i][t] && D[t + 1][j]){
                f(t + 1, j), f(i, t); 
                break;
            }
        }
    }
}

int main(){
    cin.tie(0) -> sync_with_stdio(0);

    cin >> N >> S;
    S = " " + S;
    for(ll i = 0; i <= N; i++){
        D[i + 1][i] = 1;
    }
    for(ll k = 2; k <= N; k++){
        for(ll i = 1; i <= N; i++){
            ll j = i + k - 1; if(j > N) break;
            if(k >= 2 && S[i] == S[i + 1] && D[i + 2][j]) D[i][j] = 1;
            if(k >= 2 && S[j] == S[j - 1] && D[i][j - 2]) D[i][j] = 1;
            if(k >= 2 && S[i] == S[j] && D[i + 1][j - 1]) D[i][j] = 1;

            if(k >= 3 && S[i] == S[i + 1] && S[i + 1] == S[i + 2] && D[i + 3][j]) D[i][j] = 1;
            if(k >= 3 && S[j] == S[j - 1] && S[j - 1] == S[j - 2] && D[i][j - 3]) D[i][j] = 1;
            if(k >= 3 && S[i] == S[j - 1] && S[j - 1] == S[j] && D[i + 1][j - 2]) D[i][j] = 1;
            if(k >= 3 && S[i] == S[i + 1] && S[i + 1] == S[j] && D[i + 2][j - 1]) D[i][j] = 1;

            for(ll t = i; t < j; t++){
                if(D[i][t] && D[t + 1][j]) D[i][j] = 1;
            }
        }
    }
    if(D[1][N] == 0){
        cout << -1;
    } else {
        f(1, N);
        cout << V.size() << '\n';
        for(auto e : V) cout << e.x << ' ' << e.y << '\n';
    }
}

Subtask #1
0 / 3.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 Halted 0 ms 0 KB -

Subtask #2
0 / 6.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 Halted 0 ms 0 KB -

Subtask #3
0 / 7.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 Halted 0 ms 0 KB -

Subtask #4
0 / 9.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 Halted 0 ms 0 KB -