Submission #416361

#	Time	Username	Problem	Language	Result	Execution time	Memory
416361		model_code	RPS string (innopolis2021_final_C)	C++17	37 / 100	144 ms	11484 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 500000 + 100;
int a[MAXN];
int sum[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;
}


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

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