제출 #1273444

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1273444		mat_jur	Group Photo (JOI21_ho_t3)	C++20	5 / 100	5112 ms	567804 KiB

Main

#include "bits/stdc++.h"
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else 
#define cerr if(0)cout
#define debug(X) ;
#endif
using ll = long long;
#define all(v) (v).begin(), (v).end()
#define ssize(x) int(x.size())
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back

bool sorted(const vector<int> &a) {
	for (int i = 0; i < ssize(a) - 1; ++i)
		if (a[i] >= a[i+1]+2) return false;
	return true;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);

	int n;
	cin >> n;
	vector<int> h(n);
	for (int &x : h) cin >> x;

	map<vector<int>, int> dist;
	queue<vector<int>> q;

	dist[h] = 1;
	q.push(h);

	while (ssize(q)) {
		vector<int> x = q.front();
		if (sorted(x)) {
			debug(x);
			cout << dist[x] - 1 << '\n';
			return 0;
		}
		int d = dist[x];
		q.pop();
		for (int i = 0; i < n-1; ++i) {
			swap(x[i], x[i+1]);
			if (dist[x] == 0) {
				dist[x] = d + 1;
				q.push(x);
			}
			swap(x[i], x[i+1]);
		}	
	}
	
	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 32
• Subtask 4: 0 / 20
• Subtask 5: 0 / 36