oj.uz

Submission #890428

# Submission time Handle Problem Language Result Execution time Memory
890428 2023-12-21T07:41:07 Z Matjaz Linear Garden (IOI08_linear_garden) C++14
100 / 100
 225 ms 61056 KB 
//
//  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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 448 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #6
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct

Subtask #7
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct

Subtask #8
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct

Subtask #9
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 448 KB Output is correct

Subtask #10
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #11
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2648 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2652 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4712 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 7004 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 19696 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 25956 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 32316 KB Output is correct

Subtask #22
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 38556 KB Output is correct

Subtask #23
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 60832 KB Output is correct
2 Correct 225 ms 60984 KB Output is correct
3 Correct 194 ms 61056 KB Output is correct