QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #455987 | #4356. Giraffes | nhuang685# | 10 | 4238ms | 3796kb | C++20 | 973b | 2024-06-27 05:28:36 | 2024-06-27 05:28:36 |
Judging History
answer
#include <bits/stdc++.h>
auto main() -> int {
int n;
std::cin >> n;
std::vector<int> p(n);
for (int &i : p) {
std::cin >> i;
}
std::vector<int> v(n);
std::iota(v.begin(), v.end(), 1);
int ans = n + 1;
do {
bool g = true;
for (int l = 0; l < n; ++l) {
for (int r = l; r < n; ++r) {
bool p1 = false, p2 = false;
for (int i = l + 1; i <= r - 1; ++i) {
if (v[i] < v[l] && v[i] < v[r]) {
p1 = true;
} else if (v[i] > v[l] && v[i] > v[r]) {
p2 = true;
}
if (p1 && p2) {
g = false;
break;
}
}
}
if (!g) {
break;
}
}
if (g) {
int val = 0;
for (int i = 0; i < n; ++i) {
val += (p[i] != v[i]);
}
ans = std::min(ans, val);
}
} while (std::next_permutation(v.begin(), v.end()));
std::cout << ans << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 0ms
memory: 3536kb
input:
1 1
output:
0
result:
ok single line: '0'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
2 2 1
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
3 1 2 3
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
4 3 1 4 2
output:
2
result:
ok single line: '2'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
5 3 4 5 1 2
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
6 1 5 6 2 4 3
output:
2
result:
ok single line: '2'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
6 1 6 3 4 2 5
output:
0
result:
ok single line: '0'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3604kb
input:
7 5 3 4 6 2 7 1
output:
0
result:
ok single line: '0'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3532kb
input:
7 5 3 7 1 2 6 4
output:
3
result:
ok single line: '3'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3536kb
input:
7 5 2 3 6 7 1 4
output:
2
result:
ok single line: '2'
Subtask #2:
score: 0
Time Limit Exceeded
Test #11:
score: 22
Accepted
time: 4ms
memory: 3488kb
input:
8 7 2 1 8 3 5 4 6
output:
3
result:
ok single line: '3'
Test #12:
score: 0
Accepted
time: 38ms
memory: 3604kb
input:
9 3 1 5 6 8 4 7 9 2
output:
3
result:
ok single line: '3'
Test #13:
score: 0
Accepted
time: 386ms
memory: 3608kb
input:
10 4 6 5 7 1 2 3 8 9 10
output:
2
result:
ok single line: '2'
Test #14:
score: 0
Accepted
time: 4238ms
memory: 3796kb
input:
11 2 10 3 11 1 5 8 6 4 7 9
output:
5
result:
ok single line: '5'
Test #15:
score: -22
Time Limit Exceeded
input:
12 2 7 3 1 9 4 8 12 11 6 5 10
output:
result:
Subtask #3:
score: 0
Time Limit Exceeded
Test #21:
score: 0
Time Limit Exceeded
input:
29 7 22 11 16 27 1 24 12 6 21 13 2 10 8 25 15 4 19 17 9 23 5 14 20 18 28 26 29 3
output:
result:
Subtask #4:
score: 0
Time Limit Exceeded
Test #31:
score: 0
Time Limit Exceeded
input:
2317 1841 533 998 38 1358 1204 1174 176 581 1719 550 906 35 101 442 1068 1781 601 1368 2190 2095 919 2186 1134 1814 625 90 2007 653 186 204 997 1607 1675 45 806 483 299 27 935 1070 1425 1822 1712 2074 2259 264 840 1960 1045 1742 1185 577 142 980 151 2136 2143 955 462 1373 395 1300 185 637 734 803 13...