結果
| 問題 | No.3779 L or R |
| コンテスト | |
| ユーザー |
nonon
|
| 提出日時 | 2026-11-08 18:15:21 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 279 ms / 2,000 ms |
| + 453µs | |
| コード長 | 3,276 bytes |
| 記録 | |
| コンパイル時間 | 2,555 ms |
| コンパイル使用メモリ | 346,768 KB |
| 実行使用メモリ | 6,400 KB |
| 最終ジャッジ日時 | 2026-11-08 18:15:35 |
| 合計ジャッジ時間 | 13,187 ms |
|
ジャッジサーバーID (参考情報) |
judge4_0 / judge3_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 40 |
ソースコード
// https://n-o-n-o-n.github.io/library-cpp/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<typename T>
constexpr T inf() { return numeric_limits<T>::max() / 2; }
template<typename T1, typename T2>
bool chmin(T1 &a, T2 b) { return a > b ? a = b, true : false; }
template<typename T1, typename T2>
bool chmax(T1 &a, T2 b) { return a < b ? a = b, true : false; }
template<typename ActSet>
struct dualsegtree {
using M = ActSet;
using S = typename M::S;
using F = typename M::F;
dualsegtree() : dualsegtree(0) {}
dualsegtree(int _n) : dualsegtree(vector<S>(_n, M::e())) {}
dualsegtree(const vector<S> &v) { init(v); }
void init(const vector<S> &v) {
n = v.size();
log = 0;
while ((1 << log) < n) log++;
sz = 1 << log;
d = vector<S>(sz, M::e());
for (int i = 0; i < n; i++) d[i] = v[i];
lz = vector<F>(sz, M::id());
}
void set(int p, const S &x) {
assert(0 <= p && p < n);
inner_push(p + sz);
d[p] = x;
}
void apply(int p, const F &f) {
assert(0 <= p && p < n);
p += sz;
inner_push(p);
all_apply(p, f);
}
void apply(int l, int r, const F &f) {
assert(0 <= l && l <= r && r <= n);
if (l == r) return;
l += sz, r += sz;
inner_push(l);
inner_push(r - 1);
while (l < r) {
if (l & 1) all_apply(l++, f);
if (r & 1) all_apply(--r, f);
l >>= 1;
r >>= 1;
}
}
S get(int p) {
assert(0 <= p && p < n);
inner_push(p + sz);
return d[p];
}
private:
int n, log, sz;
vector<S> d;
vector<F> lz;
void all_apply(int p, const F &f) {
if (p < sz) {
lz[p] = M::comp(f, lz[p]);
} else {
d[p - sz] = M::map(f, d[p - sz]);
}
}
void push(int p) {
all_apply(2 * p, lz[p]);
all_apply(2 * p + 1, lz[p]);
lz[p] = M::id();
}
void inner_push(int p) {
for (int i = log; i >= 1; i--) push(p >> i);
}
};
struct M {
using S = bool;
static S e() { return false; }
using F = bool;
static F comp(F f, F g) { return f ^ g; }
static F id() { return false; }
static S map(F f, S x) { return f ^ x; }
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
string S;
cin >> N >> S;
for (char fst : {'L', 'R'}) {
dualsegtree<M> seg([&] {
vector<bool> init(N);
for (int i = 0; i < N; i++) init[i] = S[i] == 'o';
return init;
} ());
string ans;
auto apply = [&] (int i, char op) -> void {
if (op == 'L') {
seg.apply(0, i + 1, true);
} else {
seg.apply(i, N, true);
}
ans.push_back(op);
};
apply(0, fst);
for (int i = 1; i < N; i++) {
if (seg.get(i) == seg.get(i - 1)) {
apply(i, 'L');
} else {
apply(i, 'R');
}
}
if (seg.get(0)) {
cout << "Yes\n";
cout << ans << '\n';
return 0;
}
}
cout << "No\n";
}
nonon