Submission #416360

#	Time	Username	Problem	Language	Result	Execution time	Memory
416360		model_code	RPS string (innopolis2021_final_C)	C++17	100 / 100	161 ms	17892 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 500000 + 100;
int a[MAXN];
int sum[MAXN][3];
int type_last[MAXN][3];
int type_first[3];
bool can[2][MAXN];
map<char, int> cv = {{'r', 0}, {'s', 1}, {'p', 2}};

string solve_t0(int t, string s) {
    int n = s.size();
    for (int i = 0; i < n; ++i) {
        a[i] = cv[s[i]];
    }
    for (int dir = 0; dir < 2; ++dir) {
        sum[0][0] = sum[0][1] = sum[0][2] = 0;
        type_first[0] = type_first[1] = type_first[2] = -1;
        for (int i = 0; i < n; ++i) {
            for (int k = 0; k < 3; ++k) {
                sum[i + 1][k] = sum[i][k];
            }
            ++sum[i + 1][a[i]];
            if (type_first[a[i]] == -1) {
                type_first[a[i]] = i;
            }
        }
        for (int i = 0; i < n; ++i) {
            can[dir][i] = 1;
            if (sum[i][(a[i] + 2) % 3] > 0 && sum[i][(a[i] + 1) % 3] == 0) {
                can[dir][i] = 0;
            }
        }
        reverse(a, a + n);
    }
    string ans;
    for (int i = 0; i < n; ++i) {
        if (can[0][i] && can[1][n - 1 - i]) {
            ans.push_back('1');
        } else {
            ans.push_back('0');
        }
    }
    return ans;
}

string solve_t1(int t, string s) {
    int n = s.size();
    for (int i = 0; i < n; ++i) {
        a[i] = cv[s[i]];
    }
    for (int dir = 0; dir < 2; ++dir) {
        sum[0][0] = sum[0][1] = sum[0][2] = 0;
        type_first[0] = type_first[1] = type_first[2] = -1;
        type_last[0][0] = type_last[0][1] = type_last[0][2] = -1;
        for (int i = 0; i < n; ++i) {
            for (int k = 0; k < 3; ++k) {
                sum[i + 1][k] = sum[i][k];
                type_last[i + 1][k] = type_last[i][k];
            }
            ++sum[i + 1][a[i]];
            type_last[i + 1][a[i]] = i;
            if (type_first[a[i]] == -1) {
                type_first[a[i]] = i;
            }
        }
        for (int i = 0; i < n; ++i) {
            can[dir][i] = 1;
            int zero = a[i];
            int one = (a[i] + 1) % 3;
            int two = (a[i] + 2) % 3;
            if (sum[i][two] > 0 && sum[i][one] == 0) {
                can[dir][i] = 0;
                continue;
            }
            if (sum[i][zero] > 0 && sum[i][two] == 0) {
                can[dir][i] = 0;
                continue;
            }
            if (type_first[one] == -1 || type_first[one] >= i) {
                if (sum[i][zero] + sum[i][two] > 0) {
                    can[dir][i] = 0;
                }
                continue;
            } else {
                int pos = type_first[one];
                int pos1 = type_last[i][one];
                if ((sum[pos][two] > 0 || sum[pos][zero] == 0)
                        && ((sum[i][two] - sum[pos + 1][two] > 0)
                            || (sum[i][zero] - sum[pos + 1][zero] == 0))) {
                    //allright
                } else {
                    if ((sum[pos1][two] > 0 || sum[pos1][zero] == 0)
                            && ((sum[i][two] - sum[pos1 + 1][two] > 0)
                                || (sum[i][zero] - sum[pos1 + 1][zero] == 0))) {
                        //allright
                    } else {
                        if (type_first[two] < i
                                && sum[type_last[i][two]][one] > sum[type_first[two]][one]) {
                            //allright
                        } else {
                            can[dir][i] = 0;
                            continue;
                        }
                    }
                }
            }
        }
        reverse(a, a + n);
    }
    string ans;
    for (int i = 0; i < n; ++i) {
        if (can[0][i] && can[1][n - 1 - i]) {
            ans.push_back('1');
        } else {
            ans.push_back('0');
        }
    }
    return ans;
}

string solve(int t, string s) {
    if (t == 0) {
        return solve_t0(t, s);
    } else {
        return solve_t1(t, s);
    }
}

int main() {
    int tests;
    cin >> tests;
    for (int i = 0; i < tests; ++i) {
        int t;
        cin >> t;
        string s;
        cin >> s;
        cout << solve(t - 1, s) << '\n';
    }
}

• Subtask 1: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 10 / 10
• Subtask 4: 11 / 11
• Subtask 5: 7 / 7
• Subtask 6: 13 / 13
• Subtask 7: 10 / 10
• Subtask 8: 33 / 33