Submission #890428

#	Time	Username	Problem	Language	Result	Execution time	Memory
890428		Matjaz	Linear Garden (IOI08_linear_garden)	C++14	100 / 100	225 ms	61056 KiB

linear_garden

//
//  IOI2008Garden.cpp
//  
//
//  Created by Matjaz Leonardis on 17/12/2023.
//

#include <iostream>
#include <string>
#include <string.h>
#include <map>
#include <assert.h>

using namespace std;

int N,M;
string s;
int dp[1000001][15];

map<pair<pair<int,int>, int>, int > vtos;
map<int,pair<pair<int,int>, int> > stov;

int nxt_state[15][2];


int next_state(int state, int incrament){
    
    //cout << state << " " << incrament << endl;
    
    if (nxt_state[state][incrament == -1 ? 0 : 1] != -2) return nxt_state[state][incrament == -1 ? 0 : 1];
    
    pair<pair<int,int>,int> st = stov[state];
    
    int max_point = st.first.first;
    int interval_length = st.first.second;
    int running_total = st.second;
    
    //cout << "(" << max_point << "," << interval_length << "," << running_total << ") + " << incrament;
    
    running_total += -incrament;
    
    if (running_total > interval_length || running_total < 0){
        interval_length++;
        if (running_total < 0) {
            max_point++;
            running_total = 0;
            
        }
    }
    
    //cout << " -> (" << max_point << "," << interval_length << "," << running_total << ")" << endl;
    
    pair<pair<int,int>,int> new_st = make_pair(make_pair(max_point, interval_length), running_total);
    
    if (vtos.count(new_st) == 0) return nxt_state[state][incrament == -1 ? 0 : 1] = -1; else return nxt_state[state][incrament == -1 ? 0 : 1] = vtos[new_st];
}

int count(int x, int state){
    
    if (x == N) return 1;
    
    if (dp[x][state] != -1) return dp[x][state];
    
    int res = 0;
    
    if (next_state(state, -1) != -1) res = (res + count(x+1,next_state(state, -1))) % M;
    if (next_state(state, 1) != -1) res = (res + count(x+1,next_state(state, 1))) % M;
    
    return dp[x][state] = res;
}

void make_state_dictionaries(){
    int state_count = 0;
    for (int interval_length = 0;interval_length <= 2; interval_length++){
        for (int max_point=0;max_point<=interval_length;max_point++){
            for (int running_total=0;running_total<=interval_length;running_total++){
                
                pair<pair<int,int>, int> st = make_pair(make_pair(max_point, interval_length), running_total);
                stov[state_count] = st;
                vtos[st] = state_count;
                state_count++;
            }
        }
    }
}


int main(){
    
    make_state_dictionaries();
    
    for (int i=0;i<15;i++){
        nxt_state[i][0] = -2;
        nxt_state[i][1] = -2;
    }
    
    cin >> N >> M >> s;
    
    for (int i=0;i<15;i++) dp[N][i] = 1;
    for (int i=N-1;i>=0;i--){
        for (int j=0;j<15;j++){
            int res = 0;
            if (next_state(j, -1) != -1) res = (res + dp[i+1][next_state(j, -1)]) % M;
            if (next_state(j, 1) != -1) res = (res + dp[i+1][next_state(j, 1)]) % M;
            dp[i][j] = res;
            //cout << i << " " << j << " " << dp[i][j] << endl;
        }
    }
    
    int res = 0;
    
    int current_state = 0;
    
    for (int i=0;i<N;i++){
        
        if (s[i] =='P' && next_state(current_state, -1) != -1) res = (res + dp[i + 1][next_state(current_state, -1)] ) % M;
        
        //cout << res << " " << next_state(current_state, -1) << endl;
        //cout << current_state << endl;
        current_state = next_state(current_state, s[i] == 'P' ? 1 : -1);
        //assert(current_state >= 0 && current_state < 15);
    }
    
    cout << (res + 1) % M << endl;
    
    
    
    return 0;
}

• Subtask 1: 2 / 2
• Subtask 2: 2 / 2
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 4 / 4
• Subtask 7: 4 / 4
• Subtask 8: 4 / 4
• Subtask 9: 4 / 4
• Subtask 10: 4 / 4
• Subtask 11: 4 / 4
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5
• Subtask 20: 5 / 5
• Subtask 21: 5 / 5
• Subtask 22: 5 / 5
• Subtask 23: 5 / 5