| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1291816 | MrDogMeat | Giraffes (JOI22_giraffes) | C++20 | 0 ms | 0 KiB |
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
///vector
#define SZ(x) (int)x.size()
const int MAXN = 8e3;
const int INF32 = 1e9;
template <class X, class Y> bool minimize(X &x, const Y &y) { if(x > y) { x = y; return 1; } return 0; }
template <class X, class Y> bool maximize(X &x, const Y &y) { if(x < y) { x = y; return 1; } return 0; }
///input
int N;
int P[MAXN+5];
namespace sub1 {
int Ans = INF32;
bool check(const vector<int>& P) {
for(int l = 0; l < N; l++)
{
for(int r = 0; r < N; r++)
{
bool cond1 = false, cond2 = false;
for(int i = l; i <= r; i++)
{
if(P[i] > P[l] && P[i] > P[r]) cond1 = true;
if(P[i] < P[l] && P[i] < P[r]) cond2 = true;
}
if(cond1 && cond2) return false;
}
}
return true;
}
void solution() {
vector<int> perm(N);
for(int i = 0; i < N; i++) {
perm[i] = i + 1;
}
do {
if(check(perm)) {
int cnt = 0;
for(int i = 1; i <= N; i++) {
if(P[i] != perm[i - 1]) cnt++;
}
Ans = min(Ans, cnt);
}
} while(next_permutation(perm.begin(), perm.end()));
cout << Ans;
}
bool check() {
return (N <= 7);
}
}
namespace sub2 {
int Ans = INF32;
int tmp[4];
void brute_force(int l, int r, int Min, int Max, int cnt) {
if(l > r) {
Ans = min(Ans, cnt);
return;
}
tmp[0] = cnt;
if(P[l] != Min) tmp[0]++;
brute_force(l + 1, r, Min + 1, Max, tmp[0]);
tmp[1] = cnt;
if(P[l] != Max) tmp[1]++;
brute_force(l + 1, r, Min, Max - 1, tmp[1]);
tmp[2] = cnt;
if(P[r] != Min) tmp[2]++;
brute_force(l, r - 1, Min + 1, Max, tmp[2]);
tmp[3] = cnt;
if(P[r] != Max) tmp[3]++;
brute_force(l, r - 1, Min, Max - 1, tmp[3]);
}
void solution() {
brute_force(1, N, 1, N, 0);
cout << Ans;
}
bool check() {
return (N <= 13);
}
}
namespace sub3 {
const int MAXN3 = 3e2;
int f[MAXN3+1][MAXN3+1][MAXN3+1];
void solution() {
memset(f, 0x3f, sizeof f);
for(int i = 1; i <= N; i++)
{
for(int j = 1; j <= N; j++)
{
f[1][i][j] = (P[i] != j);
}
}
for(int len = 2; len <= N; len++)
{
for(int i = 1; i + len - 1 <= N; i++)
{
for(int j = 1; j + len - 1 <= N; j++)
{
minimize(f[len][i][j], f[len - 1][i + 1][j + 1] + (P[i] != j));
minimize(f[len][i][j], f[len - 1][i + 1][j] + (P[i] != j + len - 1));
minimize(f[len][i][j], f[len - 1][i][j + 1] + (P[i + len - 1] != j));
minimize(f[len][i][j], f[len - 1][i][j] + (P[i + len - 1] != j + len - 1));
}
}
}
cout << f[N][1][1];
}
bool check() {
return (N <= 300);
}
}
namespace trash {
int f[MAXN+1][MAXN+1];
void solution() {
for(int i = 1; i <= N; i++)
{
for(int j = 1; j <= N; j++)
{
f[i][j] = (P[i] != j);
}
}
for(int len = 2; len <= N; len++)
{
for(int i = 1; i + len - 1 <= N; i++)
{
for(int j = 1; j + len - 1 <= N; j++)
{
int v1 = f[i + 1][j + 1] + (P[i] != j);
int v2 = f[i + 1][j] + (P[i] != j + len - 1);
int v3 = f[i][j + 1] + (P[i + len - 1] != j);
int v4 - f[i][j] + (P[i + len - 1] != j + len - 1);
f[i][j] = min({v1, v2, v3, v4});
}
}
}
cout << f[1][1];
}
bool check() {
return true;
}
}
void solution() {
cin >> N;
for(int i = 1; i <= N; i++) {
cin >> P[i];
}
if(sub1::check()) return sub1::solution();
if(sub2::check()) return sub2::solution();
if(sub3::check()) return sub3::solution();
if(trash::check()) return trash::solution();
}
#define FILE "task"
main() {
if(fopen(FILE".in","r")) {
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
}
cin.tie(nullptr)->ios_base::sync_with_stdio(false);
solution();
cerr << "\n" << clock() << " ms";
return 0;
}