oj.uz

Submission #612413

# Submission time Handle Problem Language Result Execution time Memory
612413 2022-07-29T14:30:06 Z cheissmart Giraffes (JOI22_giraffes) C++14
10 / 100
 1885 ms 1048576 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);
	};
	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;
	};

	V<V<vi>> dp(n, V<vi>());
	dp[0].PB(vi{0});
	for(int len = 1; len < n; len++) {
		for(vi q:dp[len - 1]) {
			{
				vi qq = q;
				qq.PB(len);
				dp[len].PB(qq);
			}
			{
				vi qq = q;
				qq.insert(qq.begin(), len);
				dp[len].PB(qq);
			}
		}

		for(vi q:dp[len - 1]) {
			for(int&e:q) e++;
			{
				vi qq = q;
				qq.PB(0);
				dp[len].PB(qq);
			}
			{
				vi qq = q;
				qq.insert(qq.begin(), 0);
				dp[len].PB(qq);
			}
		}
	}
	for(vi q:dp[n - 1])
		go(q);

	cout << ans << '\n';

}

Compilation message

giraffes.cpp: In function 'int main()':
giraffes.cpp:62:7: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
   62 |  auto ok = [&] (vi a) {
      |       ^~

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 2 ms 568 KB Output is correct
10 Correct 2 ms 576 KB Output is correct
11 Correct 8 ms 1808 KB Output is correct
12 Correct 28 ms 6408 KB Output is correct
13 Correct 110 ms 24832 KB Output is correct
14 Correct 451 ms 115116 KB Output is correct
15 Correct 1885 ms 476388 KB Output is correct
16 Correct 1798 ms 476424 KB Output is correct
17 Runtime error 1584 ms 1048576 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 2 ms 568 KB Output is correct
10 Correct 2 ms 576 KB Output is correct
11 Correct 8 ms 1808 KB Output is correct
12 Correct 28 ms 6408 KB Output is correct
13 Correct 110 ms 24832 KB Output is correct
14 Correct 451 ms 115116 KB Output is correct
15 Correct 1885 ms 476388 KB Output is correct
16 Correct 1798 ms 476424 KB Output is correct
17 Runtime error 1584 ms 1048576 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 2 ms 568 KB Output is correct
10 Correct 2 ms 576 KB Output is correct
11 Correct 8 ms 1808 KB Output is correct
12 Correct 28 ms 6408 KB Output is correct
13 Correct 110 ms 24832 KB Output is correct
14 Correct 451 ms 115116 KB Output is correct
15 Correct 1885 ms 476388 KB Output is correct
16 Correct 1798 ms 476424 KB Output is correct
17 Runtime error 1584 ms 1048576 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -