QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #99671 | #6352. SPPPSPSS. | upsolveupsolve | WA | 49ms | 5816kb | C++20 | 22.9kb | 2023-04-23 14:07:44 | 2023-04-23 14:07:48 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=300005,INF=1<<30;
// BIT セグ木 遅延セグ木 のみ
// from: https://gist.github.com/yosupo06/ddd51afb727600fd95d9d8ad6c3c80c9
// (based on AtCoder STL)
#include <algorithm>
#include <array>
#ifdef _MSC_VER
#include <intrin.h>
#endif
namespace atcoder {
namespace internal {
int ceil_pow2(int n) {
int x = 0;
while ((1U << x) < (unsigned int)(n)) x++;
return x;
}
int bsf(unsigned int n) {
#ifdef _MSC_VER
unsigned long index;
_BitScanForward(&index, n);
return index;
#else
return __builtin_ctz(n);
#endif
}
} // namespace internal
} // namespace atcoder
#include <cassert>
#include <numeric>
#include <type_traits>
namespace atcoder {
namespace internal {
#ifndef _MSC_VER
template <class T>
using is_signed_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value ||
std::is_same<T, __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int128 =
typename std::conditional<std::is_same<T, __uint128_t>::value ||
std::is_same<T, unsigned __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using make_unsigned_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value,
__uint128_t,
unsigned __int128>;
template <class T>
using is_integral = typename std::conditional<std::is_integral<T>::value ||
is_signed_int128<T>::value ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_signed_int = typename std::conditional<(is_integral<T>::value &&
std::is_signed<T>::value) ||
is_signed_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<(is_integral<T>::value &&
std::is_unsigned<T>::value) ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<
is_signed_int128<T>::value,
make_unsigned_int128<T>,
typename std::conditional<std::is_signed<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type>::type;
#else
template <class T> using is_integral = typename std::is_integral<T>;
template <class T>
using is_signed_int =
typename std::conditional<is_integral<T>::value && std::is_signed<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<is_integral<T>::value &&
std::is_unsigned<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<is_signed_int<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type;
#endif
template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;
template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;
template <class T> using to_unsigned_t = typename to_unsigned<T>::type;
} // namespace internal
} // namespace atcoder
#include <cassert>
#include <vector>
namespace atcoder {
template <class T> struct fenwick_tree {
using U = internal::to_unsigned_t<T>;
public:
fenwick_tree() : _n(0) {}
fenwick_tree(int n) : _n(n), data(n) {}
void add(int p, T x) {
assert(0 <= p && p < _n);
p++;
while (p <= _n) {
data[p - 1] += U(x);
p += p & -p;
}
}
T sum(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
return sum(r) - sum(l);
}
private:
int _n;
std::vector<U> data;
U sum(int r) {
U s = 0;
while (r > 0) {
s += data[r - 1];
r -= r & -r;
}
return s;
}
};
} // namespace atcoder
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
namespace atcoder {
template <class S,
S (*op)(S, S),
S (*e)(),
class F,
S (*mapping)(F, S),
F (*composition)(F, F),
F (*id)()>
struct lazy_segtree {
public:
lazy_segtree() : lazy_segtree(0) {}
lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {
log = internal::ceil_pow2(_n);
size = 1 << log;
d = std::vector<S>(2 * size, e());
lz = std::vector<F>(size, id());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
S get(int p) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
return d[p];
}
S prod(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
if (l == r) return e();
l += size;
r += size;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push(r >> i);
}
S sml = e(), smr = e();
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S all_prod() { return d[1]; }
void apply(int p, F f) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
d[p] = mapping(f, d[p]);
for (int i = 1; i <= log; i++) update(p >> i);
}
void apply(int l, int r, F f) {
assert(0 <= l && l <= r && r <= _n);
if (l == r) return;
l += size;
r += size;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push((r - 1) >> i);
}
{
int l2 = l, r2 = r;
while (l < r) {
if (l & 1) all_apply(l++, f);
if (r & 1) all_apply(--r, f);
l >>= 1;
r >>= 1;
}
l = l2;
r = r2;
}
for (int i = 1; i <= log; i++) {
if (((l >> i) << i) != l) update(l >> i);
if (((r >> i) << i) != r) update((r - 1) >> i);
}
}
template <bool (*g)(S)> int max_right(int l) {
return max_right(l, [](S x) { return g(x); });
}
template <class G> int max_right(int l, G g) {
assert(0 <= l && l <= _n);
assert(g(e()));
if (l == _n) return _n;
l += size;
for (int i = log; i >= 1; i--) push(l >> i);
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!g(op(sm, d[l]))) {
while (l < size) {
push(l);
l = (2 * l);
if (g(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}
template <bool (*g)(S)> int min_left(int r) {
return min_left(r, [](S x) { return g(x); });
}
template <class G> int min_left(int r, G g) {
assert(0 <= r && r <= _n);
assert(g(e()));
if (r == 0) return 0;
r += size;
for (int i = log; i >= 1; i--) push((r - 1) >> i);
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!g(op(d[r], sm))) {
while (r < size) {
push(r);
r = (2 * r + 1);
if (g(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
int _n, size, log;
std::vector<S> d;
std::vector<F> lz;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
void all_apply(int k, F f) {
d[k] = mapping(f, d[k]);
if (k < size) lz[k] = composition(f, lz[k]);
}
void push(int k) {
all_apply(2 * k, lz[k]);
all_apply(2 * k + 1, lz[k]);
lz[k] = id();
}
};
} // namespace atcoder
#include <algorithm>
#include <cassert>
#include <vector>
namespace atcoder {
template <class S, S (*op)(S, S), S (*e)()> struct segtree {
public:
segtree() : segtree(0) {}
segtree(int n) : segtree(std::vector<S>(n, e())) {}
segtree(const std::vector<S>& v) : _n(int(v.size())) {
log = internal::ceil_pow2(_n);
size = 1 << log;
d = std::vector<S>(2 * size, e());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
S get(int p) {
assert(0 <= p && p < _n);
return d[p + size];
}
S prod(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
S sml = e(), smr = e();
l += size;
r += size;
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S all_prod() { return d[1]; }
template <bool (*f)(S)> int max_right(int l) {
return max_right(l, [](S x) { return f(x); });
}
template <class F> int max_right(int l, F f) {
assert(0 <= l && l <= _n);
assert(f(e()));
if (l == _n) return _n;
l += size;
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!f(op(sm, d[l]))) {
while (l < size) {
l = (2 * l);
if (f(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}
template <bool (*f)(S)> int min_left(int r) {
return min_left(r, [](S x) { return f(x); });
}
template <class F> int min_left(int r, F f) {
assert(0 <= r && r <= _n);
assert(f(e()));
if (r == 0) return 0;
r += size;
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!f(op(d[r], sm))) {
while (r < size) {
r = (2 * r + 1);
if (f(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
int _n, size, log;
std::vector<S> d;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};
} // namespace atcoder
bool so(vector<int> S){
for(int i=0;i+1<si(S);i++){
if(S[i]>S[i+1]) return false;
}
return true;
}
int gutyoku(vector<int> P){
int mi=INF;
int N=si(P);
{
vector<int> S=P;
for(int t=1;t<=N+1;t++){
if(so(S)){
chmin(mi,t-1);
break;
}
if(t&1){
sort(S.begin(),S.begin()+t);
}else{
sort(S.begin()+N-t,S.end());
}
}
}
{
vector<int> S=P;
for(int t=1;t<=N+1;t++){
if(so(S)){
chmin(mi,t-1);
break;
}
if(t%2==0){
sort(S.begin(),S.begin()+t);
}else{
sort(S.begin()+N-t,S.end());
}
}
}
return mi;
}
int main(){
std::ifstream in("text.txt");
std::cin.rdbuf(in.rdbuf());
cin.tie(0);
ios::sync_with_stdio(false);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int N;cin>>N;
vector<int> P(N);
for(int i=0;i<N;i++){
cin>>P[i];P[i]--;
//P[i]=N-1-i;
}
vector<int> SAME(N+1);
for(int i=0;i<N;i++){
if(P[i]==i) SAME[i+1]++;
}
for(int i=1;i<=N;i++) SAME[i]+=SAME[i-1];
vector<int> prema=P,sufmi=P;
for(int i=1;i<N;i++) chmax(prema[i],prema[i-1]);
for(int i=N-2;i>=0;i--) chmin(sufmi[i],sufmi[i+1]);
if(so(P)){
cout<<".\n";
return 0;
}
for(int t=1;t<=(N+1)/2;t++){
{
bool f=true;
if(t-1) f&=(prema[t-2]==t-2);
if(t) f&=(sufmi[N-t]==N-t);
f&=(SAME[N-t]-SAME[t-1]==(N-t-(t-1)));
if(f){
for(int i=1;i<=t;i++){
if(abs(i-t)&1) cout<<'P';
else cout<<'S';
}
cout<<"."<<endl;
return 0;
}
}
{
bool f=true;
if(t) f&=(prema[t-1]==t-1);
if(t-1) f&=(sufmi[N-(t-1)]==N-(t-1));
f&=(SAME[N-(t-1)]-SAME[t]==(N-(t-1)-(t)));
if(f){
for(int i=1;i<=t;i++){
if(abs(i-t)&1) cout<<'S';
else cout<<'P';
}
cout<<"."<<endl;
return 0;
}
}
}
int wh=-1;
int ans=INF;
int madiff1=-INF,madiff2=-INF;
{
int mid=N/2+1;
vector<int> S=P;
if(mid-1>=0) sort(S.begin(),S.begin()+mid-1);
if(mid>=0) sort(S.begin()+N-mid,S.end());
vector<int> Q(N);
for(int i=0;i<N;i++) Q[S[i]]=i;
atcoder::fenwick_tree<int> BI(N);
int ma=0;
for(int x=0;x<N;x++){
BI.add(Q[x],1);
int a,b,c,d;
b=BI.sum(0,N-mid);
a=N-mid-b;
d=BI.sum(N-mid,N);
c=mid-d;
swap(a,b);
swap(c,d);
int sa,sb,sc,sd;
if(x+1<=N-mid){
sa=x+1;
sb=N-mid-sa;
sc=0;
sd=mid;
}else{
sa=N-mid;
sb=0;
sc=x+1-(N-mid);
sd=mid-sc;
}
int diff=max({abs(sa-a),abs(sb-b),abs(sc-c),abs(sd-d)});
chmax(madiff1,diff);
}
}
{
int mid=N/2+1;
vector<int> S=P;
if(mid-1>=0) sort(S.begin(),S.begin()+mid-1);
if(mid>=0) sort(S.begin()+N-mid,S.end());
vector<int> Q(N);
for(int i=0;i<N;i++) Q[S[i]]=i;
atcoder::fenwick_tree<int> BI(N);
int ma=0;
for(int x=0;x<N;x++){
BI.add(Q[x],1);
int a,b,c,d;
b=BI.sum(0,N-mid);
a=N-mid-b;
d=BI.sum(N-mid,N);
c=mid-d;
swap(a,b);
swap(c,d);
int sa,sb,sc,sd;
if(x+1<=N-mid){
sa=x+1;
sb=N-mid-sa;
sc=0;
sd=mid;
}else{
sa=N-mid;
sb=0;
sc=x+1-(N-mid);
sd=mid-sc;
}
int diff=max({abs(sa-a),abs(sb-b),abs(sc-c),abs(sd-d)});
//cout<<x<<" "<<max({abs(sa-a),abs(sb-b),abs(sc-c),abs(sd-d)})<<endl;
if(diff<madiff1-5) continue;
if(b==0||c==0){
chmax(ma,mid);
continue;
}
//cout<<x<<" "<<a<<" "<<b<<" "<<c<<" "<<d<<endl;
//if(x&1) continue;
for(int t=1;;t++){
int len=mid+t;
if(t&1){
if(a+b+c<=len){
chmax(ma,len);
break;
}else{
a=len-b;
c=N-len-d;
}
}else{
if(b+c+d<=len){
chmax(ma,len);
break;
}else{
d=len-c;
b=N-len-a;
}
}
}
}
if(chmin(ans,ma)) wh=0;
}
{
int mid=N/2+1;
vector<int> S=P;
if(mid-1>=0) sort(S.begin()+N-(mid-1),S.end());
if(mid>=0) sort(S.begin(),S.begin()+mid);
vector<int> Q(N);
for(int i=0;i<N;i++) Q[S[i]]=i;
atcoder::fenwick_tree<int> BI(N);
int ma=0;
for(int x=0;x<N;x++){
BI.add(Q[x],1);
int a,b,c,d;
b=BI.sum(0,mid);
a=mid-b;
d=BI.sum(mid,N);
c=N-mid-d;
swap(a,b);
swap(c,d);
int sa,sb,sc,sd;
if(x+1<=mid){
sa=x+1;
sb=mid-sa;
sc=0;
sd=N-mid;
}else{
sa=mid;
sb=0;
sc=x+1-(mid);
sd=N-mid-sc;
}
int diff=max({abs(sa-a),abs(sb-b),abs(sc-c),abs(sd-d)});
chmax(madiff2,diff);
}
}
{
int mid=N/2+1;
vector<int> S=P;
if(mid-1>=0) sort(S.begin()+N-(mid-1),S.end());
if(mid>=0) sort(S.begin(),S.begin()+mid);
vector<int> Q(N);
for(int i=0;i<N;i++) Q[S[i]]=i;
atcoder::fenwick_tree<int> BI(N);
int ma=0;
for(int x=0;x<N;x++){
BI.add(Q[x],1);
int a,b,c,d;
b=BI.sum(0,mid);
a=mid-b;
d=BI.sum(mid,N);
c=N-mid-d;
swap(a,b);
swap(c,d);
int sa,sb,sc,sd;
if(x+1<=mid){
sa=x+1;
sb=mid-sa;
sc=0;
sd=N-mid;
}else{
sa=mid;
sb=0;
sc=x+1-(mid);
sd=N-mid-sc;
}
int diff=max({abs(sa-a),abs(sb-b),abs(sc-c),abs(sd-d)});
if(diff<madiff2-5) continue;
if(b==0||c==0){
chmax(ma,mid);
continue;
}
//if(x&1) continue;
for(int t=1;;t++){
//cout<<x<<" "<<a<<" "<<b<<" "<<c<<" "<<d<<endl;
int len=mid+t;
if(t%2==0){
if(a+b+c<=len){
chmax(ma,len);
break;
}else{
a=len-b;
c=N-len-d;
}
}else{
if(b+c+d<=len){
chmax(ma,len);
break;
}else{
d=len-c;
b=N-len-a;
}
}
}
}
if(chmin(ans,ma)) wh=1;
}
//cout<<ans<<endl;
//return ans;
if(wh==0){
for(int i=1;i<=ans;i++){
if(abs(i-(N/2+1))&1) cout<<'P';
else cout<<'S';
}
cout<<"."<<endl;
}else{
for(int i=1;i<=ans;i++){
if(abs(i-(N/2+1))&1) cout<<'S';
else cout<<'P';
}
cout<<"."<<endl;
}
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3500kb
input:
3 1 2 3
output:
.
result:
ok OK 0 operations
Test #2:
score: 0
Accepted
time: 0ms
memory: 3476kb
input:
2 2 1
output:
PS.
result:
ok OK 2 operations
Test #3:
score: 0
Accepted
time: 2ms
memory: 3504kb
input:
9 3 2 4 1 5 6 7 9 8
output:
SPSP.
result:
ok OK 4 operations
Test #4:
score: 0
Accepted
time: 1ms
memory: 3456kb
input:
10 2 9 5 7 10 6 3 1 8 4
output:
PSPSPSPS.
result:
ok OK 8 operations
Test #5:
score: 0
Accepted
time: 0ms
memory: 3452kb
input:
13 9 8 5 4 3 2 1 13 12 11 10 7 6
output:
PSPSPSPS.
result:
ok OK 8 operations
Test #6:
score: 0
Accepted
time: 2ms
memory: 3476kb
input:
20 17 6 15 14 4 10 18 7 13 8 2 12 1 19 20 3 11 16 5 9
output:
SPSPSPSPSPSPSP.
result:
ok OK 14 operations
Test #7:
score: 0
Accepted
time: 2ms
memory: 3504kb
input:
100 98 85 81 18 27 10 68 48 19 2 55 51 61 20 91 54 35 22 83 75 8 5 17 23 21 95 37 15 92 50 78 82 44 39 26 87 52 66 70 74 89 4 59 40 12 88 86 43 14 80 53 46 63 3 36 97 60 58 57 96 11 67 99 41 34 47 71 72 73 79 9 94 6 1 77 25 31 7 45 100 90 32 24 13 76 16 93 38 29 69 42 84 30 28 33 56 49 62 64 65
output:
SPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPS.
result:
ok OK 57 operations
Test #8:
score: 0
Accepted
time: 2ms
memory: 3464kb
input:
1000 668 554 210 852 617 846 561 95 341 893 276 224 287 1000 356 362 897 205 369 654 181 590 339 377 346 557 382 593 55 62 126 899 49 509 977 585 614 232 865 800 790 292 219 957 379 914 946 246 294 403 940 517 768 623 376 624 331 353 887 626 424 449 115 628 569 809 956 942 300 894 61 936 678 779 549...
output:
SPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSP...
result:
ok OK 523 operations
Test #9:
score: -100
Wrong Answer
time: 49ms
memory: 5816kb
input:
100000 30619 15529 4854 9258 46894 29948 59533 56945 19473 7608 42291 95532 80537 83105 70434 68130 89221 96367 26768 43837 54765 52814 88446 14950 63224 63479 11957 41446 38702 8466 85556 57724 50097 29014 17961 65178 88627 96815 80115 79096 19625 2979 51033 68224 48649 96250 3406 96433 22584 79610...
output:
SPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSP...
result:
wrong answer the permutation is not sorted