Submission #75823092

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int r(int n, int i, int offset) {
	if (offset < 0) {
		return (i + offset < 0) ? i + offset + n : i + offset;
	}
	else if (offset > 0){
		return (i + offset) % n;
	}
	return i;
}

bool f(vector<int>& v, int i) {
	int pr = r(v.size(), i, -1);
	int ppr = r(v.size(), i, -2);
	int nx = r(v.size(), i, 1);
	int nnx = r(v.size(), i, 2);
	if ((v[pr] == v[ppr]) ||
		(v[pr] == v[nx]) ||
		(v[nx] == v[nnx]))
	{
		return true;
	}
	return false;
}




int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int t;
	cin >> t;

	while (t--) {

		int n;
		string s;
		cin >> n >> s;

		vector<int>v(n);
		vector<bool>known(n, false); // 자기거 앎?
		for (int i = 0; i < n; i++) {
			v[i] = (s[i] == 'O') ? 1 : -1;
		}

		vector<int>ans(n, -1);
		int round;

		for (int k = 1; k <= n/2; k++) {
			round = k;
			if (n == 3 && k == 2) break;
			for (int i = 0; i < n; i++) {
				if (known[i] == true) continue;
				vector<int> temp = v;
				temp[i] = -67;
				if (f(temp, i)) { //단독유추가능?
					known[i] = true;
				}
				else {
					if (known[r(n, i, -1)] == true && ans[r(n, i, -1)] != round) { //왼쪽꺼 보고 내꺼 유추 가능한지
						if (v[r(n, r(n, i, -1), -2)] != v[r(n, r(n, i, -1), -1)]) {
							known[i] = true;
						}
					}
					if (known[r(n, i, 1)] == true && ans[r(n, i, 1)] != round) { //오른쪽 보고 ''
						if (v[r(n, r(n, i, 1), 2)] != v[r(n, r(n, i, 1), 1)]) {
							known[i] = true;
						}
					}
					if (known[r(n, i, -2)] == true && ans[r(n, i, -2)] != round) { //왼왼쪽 ''
						if (v[r(n, r(n, i, -2), -2)] != v[r(n, r(n, i, -2), -1)] &&
							v[r(n, r(n, i, -2), -1)] != v[r(n, r(n, i, -2), 1)]) {
							known[i] = true;
						}
					}
					if (known[r(n, i, 2)] == true && ans[r(n, i, 2)] != round) { //오오른쪽 ''
						if (v[r(n, r(n, i, 2), 2)] != v[r(n, r(n, i, 2), 1)] &&
							v[r(n, r(n, i, 2), -1)] != v[r(n, r(n, i, 2), 1)]) {
							known[i] = true;
						}
					}


				}
				if (known[i] == true) ans[i] = round;
			}
		}

		if (n == 3) {
			for (int i = 0; i < n; i++) {
				if (ans[i] == -1) {
					ans[i] = 2;
				}
			}
		}

		for (int i = 0; i < n; i++) {
			cout << ans[i] << " ";
		}
		cout << "\n";





	}



	return 0;
}

Submission Info

Judge Result