Submission #612369

#	Time	Username	Problem	Language	Result	Execution time	Memory
612369		8e7	Giraffes (JOI22_giraffes)	C++17	32 / 100	7092 ms	304 KiB

giraffes

//Challenge: Accepted
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define double long double
#define maxn 2005
#define pii pair<ll, ll>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const ll inf = 1LL<<50;

int p[maxn];
int n;

int ans = 10000;
void build(int se, vector<int> v, int cnt) {
	if (v.size() == n) {
		ans = min(ans, cnt);
		return;
	}
	for (int i = 0;i < n;i++) {
		if (!((se>>i) & 1)) {
			int to = se + (1<<i);
			int mi = i, ma = i;
			bool good = 1;
			for (int j = (int)v.size() - 1;j >= 0;j--) {
				if (mi != i && ma != i && mi < v[j] && v[j] < ma) {
					good = 0;
					break;
				}
				mi = min(mi, v[j]);
				ma = max(ma, v[j]);
			}
			if (good) {
				vector<int> tv = v;
				tv.push_back(i);
				int tc = cnt;
				if (p[v.size()] != i) tc++; 
				build(to, tv, tc);
			}
		}
	}
}

int main() {
	io
	cin >> n;
	for (int i = 0;i < n;i++) cin >> p[i], p[i]--;
	vector<int> ini;
	build(0, ini, 0);
	cout << ans << "\n";
}

Compilation message (stderr)

giraffes.cpp: In function 'void build(int, std::vector<int>, int)':
giraffes.cpp:30:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |  if (v.size() == n) {
      |      ~~~~~~~~~^~~~

• Subtask 1: 10 / 10
• Subtask 2: 22 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 41