Submission #942133

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
942133	2024-03-10T09:43:34 Z	dsyz	Group Photo (JOI21_ho_t3)	C++17	5 / 100	5000 ms	460 KB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N;
	cin>>N;
	ll H[N], arr[N];
	for(ll i = 0;i < N;i++){
		cin>>H[i];
		arr[i] = H[i];
	}
	sort(arr,arr + N);
	ll ans = 1e18;
	do{
		bool ok = 1;
		for(ll i = 1;i < N;i++){
			if(arr[i - 1] >= arr[i] + 2){
				ok = 0;
			}
		}
		if(!ok) continue;
		ll sum = 0;
		ll tmp[N];
		for(ll i = 0;i < N;i++){
			tmp[i] = H[i];
		}
		for(ll i = 0;i < N;i++){
			ll pos = 0;
			for(ll j = 0;j < N;j++){
				if(tmp[j] == arr[i]){
					pos = j;
				}
			}
			while(pos > i){
				swap(tmp[pos - 1],tmp[pos]);
				pos--;
				sum++;
			}
			while(pos < i){
				swap(tmp[pos],tmp[pos + 1]);
				pos++;
				sum++;
			}
		}
		ans = min(ans,sum);
	}while(next_permutation(arr,arr + N));
	cout<<ans<<'\n';
}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	460 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	4 ms	348 KB	Output is correct
8	Correct	4 ms	348 KB	Output is correct
9	Correct	4 ms	348 KB	Output is correct
10	Correct	4 ms	348 KB	Output is correct

Subtask #2

0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	460 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	4 ms	348 KB	Output is correct
8	Correct	4 ms	348 KB	Output is correct
9	Correct	4 ms	348 KB	Output is correct
10	Correct	4 ms	348 KB	Output is correct
11	Execution timed out	5031 ms	348 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Subtask #3

0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	460 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	4 ms	348 KB	Output is correct
8	Correct	4 ms	348 KB	Output is correct
9	Correct	4 ms	348 KB	Output is correct
10	Correct	4 ms	348 KB	Output is correct
11	Execution timed out	5031 ms	348 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Subtask #4

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	460 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	4 ms	348 KB	Output is correct
8	Correct	4 ms	348 KB	Output is correct
9	Correct	4 ms	348 KB	Output is correct
10	Correct	4 ms	348 KB	Output is correct
11	Execution timed out	5031 ms	348 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Subtask #5

0 / 36.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	460 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	4 ms	348 KB	Output is correct
8	Correct	4 ms	348 KB	Output is correct
9	Correct	4 ms	348 KB	Output is correct
10	Correct	4 ms	348 KB	Output is correct
11	Execution timed out	5031 ms	348 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-