QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #137127 | #6352. SPPPSPSS. | berarchegas# | WA | 2ms | 7712kb | C++20 | 3.2kb | 2023-08-09 22:07:58 | 2023-08-09 22:08:00 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
mt19937 rng((int) chrono::steady_clock::now().time_since_epoch().count());
const int MOD = 1e9 + 7;
const int MAXN = 1e6 + 5;
const ll INF = 2e18;
int v[MAXN], temp[MAXN];
int marc[MAXN];
int n;
bool testp(int m) {
for(int i = 1; i <= n; i++) {
temp[i] = v[i]; marc[i] = 0;
}
int cur;
if(m >= 3) {
for(int i = 1; i <= m - 2; i++) {
marc[temp[i]]++;
}
cur = 1;
for(int i = 1; i <= n; i++) {
if(marc[i] == 1) {
temp[cur] = i;
marc[i] = 0;
cur++;
}
}
}
for(int i = n; i > n - m + 1; i--) {
marc[temp[i]]++;
}
cur = n - m + 2;
for(int i = 1; i <= n; i++) {
if(marc[i] == 1) {
temp[cur] = i;
marc[i] = 0;
cur++;
}
}
for(int i = 1; i <= m; i++) {
marc[temp[i]]++;
}
cur = 1;
for(int i = 1; i <= n; i++) {
if(marc[i] == 1) {
temp[cur] = i;
marc[i] = 0;
cur++;
}
}
bool ok = true;
for(int i = 1; i <= n; i++) {
if(temp[i] != i) ok = false;
}
return ok;
}
bool tests(int m) {
for(int i = 1; i <= n; i++) {
temp[i] = v[i]; marc[i] = 0;
}
int cur;
if(m >= 3) {
for(int i = n; i >= n - m + 3; i--) {
marc[temp[i]]++;
}
cur = n - m + 3;
for(int i = 1; i <= n; i++) {
if(marc[i] == 1) {
temp[cur] = i;
marc[i] = 0;
cur++;
}
}
}
for(int i = 1; i < m; i++) {
marc[temp[i]]++;
}
cur = 1;
for(int i = 1; i <= n; i++) {
if(marc[i] == 1) {
temp[cur] = i;
marc[i] = 0;
cur++;
}
}
for(int i = n; i >= n - m + 1; i--) {
marc[temp[i]]++;
}
cur = n - m + 1;
for(int i = 1; i <= n; i++) {
if(marc[i] == 1) {
temp[cur] = i;
marc[i] = 0;
cur++;
}
}
bool ok = true;
for(int i = 1; i <= n; i++) {
if(temp[i] != i) ok = false;
}
return ok;
}
bool test(int m) {
if(testp(m)) return true;
if(tests(m)) return true;
return false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
bool ok = true;
for(int i = 1; i <= n; i++) {
cin >> v[i];
if(v[i] != i) ok = false;
}
if(ok) {
cout << ".\n";
return 0;
}
int ini = 2, fim = n;
while(ini < fim) {
int m = (ini + fim) / 2;
if(test(m)) fim = m;
else ini = m + 1;
}
if(ini == 2) {
if(testp(ini)) cout << "SP.\n";
else cout << "PS.\n";
}
else if(testp(ini)) {
for(int i = 1; i < ini - 1; i++) cout << 'P';
cout << "SP.\n";
}
else {
for(int i = 1; i < ini - 1; i++) cout << 'S';
cout << "PS.\n";
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5488kb
input:
3 1 2 3
output:
.
result:
ok OK 0 operations
Test #2:
score: 0
Accepted
time: 0ms
memory: 7580kb
input:
2 2 1
output:
SP.
result:
ok OK 2 operations
Test #3:
score: 0
Accepted
time: 0ms
memory: 7712kb
input:
9 3 2 4 1 5 6 7 9 8
output:
PPSP.
result:
ok OK 4 operations
Test #4:
score: 0
Accepted
time: 1ms
memory: 7592kb
input:
10 2 9 5 7 10 6 3 1 8 4
output:
PPPPPPSP.
result:
ok OK 8 operations
Test #5:
score: 0
Accepted
time: 2ms
memory: 7668kb
input:
13 9 8 5 4 3 2 1 13 12 11 10 7 6
output:
SSSSSSPS.
result:
ok OK 8 operations
Test #6:
score: 0
Accepted
time: 1ms
memory: 7592kb
input:
20 17 6 15 14 4 10 18 7 13 8 2 12 1 19 20 3 11 16 5 9
output:
PPPPPPPPPPPPSP.
result:
ok OK 14 operations
Test #7:
score: -100
Wrong Answer
time: 2ms
memory: 7640kb
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:
PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPSP.
result:
wrong answer Jury (57) found answer better than participant (63)