# C++ accepted solution with simulation O(N*logN).

• Every round at least half of the senate will die.
I do the simulation until only one person from the senate is alive.
Each simulation is O(n) (the kill index is constantly increasing).

``````class Solution {
public:
int N, N2;
bool kill(int idx, vector<bool>& killed) {
idx = (idx < N) ? (idx + N) : idx;
bool res = killed[idx] != true;
killed[idx] = killed[idx % N] = true;
return res;
}

string predictPartyVictory(string senate) {
N = senate.size();
senate += senate;
N2 = senate.size();
vector<bool> killed(N2, false);

bool flag = true;
while (flag) {
flag = false;
int j1, j2 = j1 = 0;
for (int i = 0; i < N; ++i) {
if (killed[i]) continue;
if (senate[i] == 'D') {
if (j1 < i + 1) j1 = i + 1;
while (j1 < N2 && (senate[j1] == 'D' || killed[j1])) {
j1++;
}
if (j1 == N2) break;
flag = true;
kill(j1, killed);
} else if (senate[i] == 'R') {
if (j2 < i + 1) j2 = i + 1;
while (j2 < N2 && (senate[j2] == 'R' || killed[j2])) {
j2++;
}
if (j2 == N2) break;
flag = true;
kill(j2, killed);
}
}
}
//for (auto c : killed) cout << c << ',';
for (int i = 0; i < N; ++i) {
if (!killed[i]) return senate[i] == 'R'