QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #182860 | #5190. 小 E 爱消除 | james1BadCreeper | AC ✓ | 342ms | 13228kb | C++14 | 2.4kb | 2023-09-18 17:26:50 | 2023-09-18 17:26:50 |
Judging History
answer
#include <bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
const int INF = 1e9;
mt19937 Rand(time(0));
int n;
int a[55], v[55], s[55];
pii operator+ (const pii &a, const pii &b) { return make_pair(a.fi + b.fi, a.se + b.se); }
int f[55][55][55][55];
int F(int l1, int r1, int l2, int r2) {
if (l1 > r1 && l2 > r2) return 0;
if ((r1 - l1 + r2 - l2 & 1) || (s[r1] ^ s[l1 - 1] ^ s[r2] ^ s[l2 - 1])) return INF;
int &ans = f[l1][r1][l2][r2];
if (ans) return ans; ans = INF;
for (int i = l1 + 1; i <= r1; ++i) if (a[l1] == a[i]) for (int j = l2 - 1; j <= r2; ++j)
ans = std::min(ans, std::max({2, F(l1 + 1, i - 1, j + 1, r2) + 1, F(i + 1, r1, l2, j)}));
for (int i = l2; i <= r2; ++i) if (a[l1] == a[i]) for (int j = l1 + 1; j <= r1 + 1; ++j)
ans = std::min(ans, std::max({2, F(l1 + 1, j - 1, i + 1, r2) + 1, F(j, r1, l2, i - 1)}));
for (int i = l1; i <= r1; ++i) if (a[r2] == a[i]) for (int j = l2 - 1; j <= r2 - 1; ++j)
ans = std::min(ans, std::max({2, F(l1, i - 1, j + 1, r2 - 1) + 1, F(i + 1, r1, l2, j)}));
for (int i = l2; i <= r2 - 1; ++i) if (a[r2] == a[i]) for (int j = l1; j <= r1 + 1; ++j)
ans = std::min(ans, std::max({2, F(l1, j - 1, i + 1, r2 - 1) + 1, F(j, r1, l2, i - 1)}));
return ans;
}
pii g[55][55];
pii G(int l, int r) {
if (l > r) return make_pair(0, 0);
if (g[l][r].se) return g[l][r];
auto &ans = g[l][r];
ans = min(G(l + 1, r), G(l, r - 1)) + make_pair(1, 1);
for (int i = l + 1; i <= r; ++i) if (a[l] == a[i]) for (int j = l + 1; j <= r; ++j) {
int x = F(l + 1, min(i, j) - 1, max(i, j) + 1, r);
if (x == INF) continue;
auto tmp = j < i ? G(j, i - 1) : G(i + 1, j);
ans = min(ans, make_pair(tmp.fi, max({2, tmp.se, x + 1})));
}
for (int i = l; i <= r - 1; ++i) if (a[i] == a[r]) for (int j = l; j <= r - 1; ++j) {
int x = F(l, min(i, j) - 1, max(i, j) + 1, r - 1);
if (x == INF) continue;
auto tmp = j < i ? G(j, i - 1) : G(i + 1, j);
ans = min(ans, make_pair(tmp.fi, max({2, tmp.se, x + 1})));
}
return ans;
}
int main(void) {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", a + i), v[a[i]] = Rand();
for (int i = 1; i <= n; ++i) s[i] = s[i - 1] ^ v[a[i]];
printf("%d %d\n", G(1, n).fi, G(1, n).se);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 100ms
memory: 12968kb
input:
50 14 31 14 31 14 31 14 14 14 31 14 14 14 31 31 31 14 31 31 31 31 14 31 14 31 14 31 14 31 31 14 31 14 14 31 31 14 31 31 14 14 31 31 14 31 31 14 14 31 14
output:
0 3
result:
ok single line: '0 3'
Test #2:
score: 0
Accepted
time: 33ms
memory: 12008kb
input:
50 1 18 18 18 50 1 50 1 18 18 50 18 18 18 50 1 50 1 18 50 18 50 50 50 18 18 18 50 50 1 18 18 18 18 50 1 50 1 50 50 18 1 50 50 50 1 1 18 18 50
output:
2 3
result:
ok single line: '2 3'
Test #3:
score: 0
Accepted
time: 6ms
memory: 8020kb
input:
50 6 5 13 5 36 13 29 29 29 5 36 5 6 13 5 5 6 5 29 29 5 5 29 5 13 6 13 13 5 13 5 13 29 39 39 39 6 6 6 39 5 39 13 13 29 13 5 6 6 39
output:
2 8
result:
ok single line: '2 8'
Test #4:
score: 0
Accepted
time: 2ms
memory: 4880kb
input:
50 50 34 43 39 50 21 50 27 34 7 50 2 7 27 2 43 21 43 7 7 39 34 7 32 50 34 50 34 32 34 32 34 21 27 7 2 50 34 27 39 39 7 21 21 7 27 39 50 34 7
output:
10 11
result:
ok single line: '10 11'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3924kb
input:
50 10 49 41 28 26 11 5 24 29 18 39 38 13 16 26 37 40 25 50 44 26 13 49 24 2 6 4 3 38 4 15 37 41 37 34 25 20 24 15 38 26 15 26 10 6 7 47 13 31 6
output:
38 38
result:
ok single line: '38 38'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3952kb
input:
1 1
output:
1 1
result:
ok single line: '1 1'
Test #7:
score: 0
Accepted
time: 342ms
memory: 13228kb
input:
50 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22
output:
0 2
result:
ok single line: '0 2'
Test #8:
score: 0
Accepted
time: 0ms
memory: 6172kb
input:
50 19 40 9 10 19 40 12 9 19 19 7 9 9 7 12 19 19 7 19 40 46 12 10 46 12 7 19 7 19 12 7 10 7 46 12 7 9 9 10 12 7 7 10 46 19 12 7 9 10 40
output:
6 9
result:
ok single line: '6 9'
Test #9:
score: 0
Accepted
time: 2ms
memory: 7036kb
input:
50 26 9 1 1 1 29 1 9 26 20 20 21 1 26 21 21 1 1 29 26 29 21 1 1 21 1 26 21 21 1 26 20 9 1 29 29 29 21 29 20 29 21 20 29 1 1 9 9 29 29
output:
4 5
result:
ok single line: '4 5'
Test #10:
score: 0
Accepted
time: 2ms
memory: 5260kb
input:
50 12 45 45 50 24 45 45 5 50 50 24 24 45 31 5 9 24 24 31 24 24 12 45 5 12 12 32 45 9 45 32 31 5 50 12 32 24 50 5 9 32 50 9 31 9 9 32 31 50 45
output:
14 14
result:
ok single line: '14 14'
Test #11:
score: 0
Accepted
time: 93ms
memory: 12960kb
input:
50 42 32 42 42 42 42 42 32 42 32 42 42 42 42 42 42 32 32 32 32 42 42 32 32 42 32 42 32 42 42 32 32 42 32 32 32 42 32 32 32 32 42 42 32 32 42 32 42 32 42
output:
0 3
result:
ok single line: '0 3'
Test #12:
score: 0
Accepted
time: 2ms
memory: 5780kb
input:
50 47 47 12 38 43 9 12 49 47 47 38 43 47 43 37 38 9 12 38 38 47 37 9 9 37 38 38 12 47 12 12 24 49 43 43 43 49 49 47 43 38 24 47 47 43 9 12 37 9 12
output:
0 7
result:
ok single line: '0 7'
Test #13:
score: 0
Accepted
time: 5ms
memory: 7836kb
input:
50 2 40 16 35 7 38 40 40 40 7 16 7 40 2 38 16 16 38 2 38 40 2 40 2 40 7 2 2 2 40 2 38 40 38 16 35 2 2 38 40 7 7 7 2 2 16 40 38 2 7
output:
0 6
result:
ok single line: '0 6'
Test #14:
score: 0
Accepted
time: 0ms
memory: 5976kb
input:
50 37 37 36 15 13 13 36 36 13 13 35 36 36 3 13 29 37 36 36 21 35 13 35 35 36 21 15 15 36 37 37 21 37 21 21 29 3 3 35 36 29 29 3 36 36 3 3 35 15 21
output:
0 5
result:
ok single line: '0 5'
Test #15:
score: 0
Accepted
time: 1ms
memory: 4844kb
input:
50 37 9 8 16 16 9 9 30 36 6 37 16 23 30 8 50 1 9 16 1 23 23 1 1 22 38 38 16 1 37 8 16 1 9 9 8 8 1 22 30 22 23 37 6 36 30 8 50 1 22
output:
0 9
result:
ok single line: '0 9'
Test #16:
score: 0
Accepted
time: 80ms
memory: 12328kb
input:
50 5 5 5 5 5 5 5 5 5 5 5 5 3 3 4 4 5 4 4 5 4 4 5 4 4 5 4 4 5 4 4 5 4 4 5 4 4 5 4 4 5 4 4 5 4 4 5 4 4 5
output:
0 2
result:
ok single line: '0 2'
Test #17:
score: 0
Accepted
time: 1ms
memory: 4884kb
input:
50 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 47 24 1 49 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
output:
6 25
result:
ok single line: '6 25'
Test #18:
score: 0
Accepted
time: 0ms
memory: 5020kb
input:
50 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 47 24 1 2 47 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
output:
0 25
result:
ok single line: '0 25'
Test #19:
score: 0
Accepted
time: 0ms
memory: 6120kb
input:
50 1 2 3 4 5 6 2 3 4 5 6 7 3 4 5 6 7 8 4 5 6 7 8 9 5 1 2 3 4 5 6 2 3 4 5 6 7 3 4 5 6 7 8 4 5 6 7 8 9 5
output:
0 14
result:
ok single line: '0 14'
Test #20:
score: 0
Accepted
time: 5ms
memory: 8180kb
input:
50 1 3 5 7 9 11 3 7 3 9 11 1 5 1 1 9 7 7 3 5 3 7 11 9 5 7 1 3 11 5 9 3 5 11 9 1 11 5 1 7 7 3 9 11 9 3 5 11 9 7
output:
4 8
result:
ok single line: '4 8'