oj.uz

Submission #612394

# Submission time Handle Problem Language Result Execution time Memory
612394 2022-07-29T14:05:44 Z cheissmart Giraffes (JOI22_giraffes) C++14
10 / 100
 7000 ms 316 KB 
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

string _reset = "\u001b[0m", _yellow = "\u001b[33m", _bold = "\u001b[1m";
void DBG() { cerr << "]" << _reset << endl; }
template<class H, class...T> void DBG(H h, T ...t) {
	cerr << to_string(h);
	if(sizeof ...(t)) cerr << ", ";
	DBG(t...);
}
#ifdef CHEISSMART
#define debug(...) cerr << _yellow << _bold << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define debug(...)
#endif

const int INF = 1e9 + 7;

signed main()
{
	IO_OP;

	int n;
	cin >> n;
	vi p(n);
	for(int i = 0; i < n; i++) {
		cin >> p[i];
		p[i]--;
	}
	int ans = INF;

	auto go = [&] (vi q) {
		vi iq(n);
		for(int i = 0; i < n; i++)
			iq[q[i]] = i;
		vi pp;
		for(int i:p)
			pp.PB(iq[i]);

		int tt = 0;
		for(int i = 0; i < n; i++) {
			if(pp[i] != i) {
				tt++;
			}
		}
		ans = min(ans, tt);
	};
	vi q(n); iota(ALL(q), 0);

	auto ok = [&] (vi a) {
		int l = 0, r = n - 1, lb = 0, rb = n - 1;
		while(r - l + 1 >= 4) {
			if(a[l] != lb && a[l] != rb && a[r] != lb && a[r] != rb)
				return false;
			if(a[l] == lb)
				l++, lb++;
			else if(a[l] == rb)
				l++, rb--;
			else if(a[r] == lb)
				r--, lb++;
			else
				r--, rb--;
		}
		return true;
	};

	do {
		if(ok(q))
			go(q);
	} while(next_permutation(ALL(q)));

	cout << ans << '\n';

}

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 288 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 3 ms 212 KB Output is correct
12 Correct 15 ms 316 KB Output is correct
13 Correct 124 ms 296 KB Output is correct
14 Correct 1295 ms 296 KB Output is correct
15 Execution timed out 7069 ms 212 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 288 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 3 ms 212 KB Output is correct
12 Correct 15 ms 316 KB Output is correct
13 Correct 124 ms 296 KB Output is correct
14 Correct 1295 ms 296 KB Output is correct
15 Execution timed out 7069 ms 212 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 288 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 3 ms 212 KB Output is correct
12 Correct 15 ms 316 KB Output is correct
13 Correct 124 ms 296 KB Output is correct
14 Correct 1295 ms 296 KB Output is correct
15 Execution timed out 7069 ms 212 KB Time limit exceeded
16 Halted 0 ms 0 KB -