Submission #1088811

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088811		pokmui9909	Good Game (CCO22_day2problem3)	C++17	0 / 25	0 ms	348 KiB

Main

#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
• Subtask 2: 0 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 9