Submission #75816032

---

Source Code Expand

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define sz(x) (int)(x).size()
using namespace std;
typedef long long ll;

int main() {
    fastio; int T; cin >> T;
    for (int tc = 0; tc < T; tc++) {
        int N; string S; cin >> N >> S;
        vector<int> ans(N);
        queue<pair<int,int>> q;
        for (int i = 0; i < N; i++) {
            if (S[(i-1+N)%N] == S[(i+1)%N] || S[(i-2+N)%N] == S[(i-1+N)%N] || S[(i+1)%N] == S[(i+2)%N]) {
                q.push({ i, 1 }); ans[i] = 1;
            }
        }
        while (!q.empty()) {
            auto [i, t] = q.front(); q.pop();
            if (!ans[(i-1+N)%N]) {
                ans[(i-1+N)%N] = t+1;
                q.push({ (i-1+N)%N, t+1 });
            }
            if (!ans[(i+1)%N]) {
                ans[(i+1)%N] = t+1;
                q.push({ (i+1)%N, t+1 });
            }
        }
        for (int i = 0; i < N; i++) cout << (ans[i] == 0 ? -1 : ans[i]) << " ";
        cout << "\n";
    }
    return 0;
}

Submission Info

Judge Result