Submission #1088817

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088817		pokmui9909	Good Game (CCO22_day2problem3)	C++17	0 / 25	1 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;
    //cin >> S; N = S.size();
    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';

        ll F = N;
        for(auto e : V){
            string T; 
            for(ll i = 1; i < e.x; i++) T.push_back(S[i]);
            for(ll i = e.x + e.y; i < S.size(); i++) T.push_back(S[i]);
            S = " " + T;
            F -= e.y;
        }
        assert(F == 0 && S.size() == 1);
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:71:37: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |             for(ll i = e.x + e.y; i < S.size(); i++) T.push_back(S[i]);
      |                                   ~~^~~~~~~~~~

• Subtask 1: 0 / 3
• Subtask 2: 0 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 9