Submission #697363

#	Time	Username	Problem	Language	Result	Execution time	Memory
697363		micjan	Group Photo (JOI21_ho_t3)	C++14	12 / 100	179 ms	296 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<pll> vll;

#define st first
#define nd second
#define FOR(i,j,k) for(auto i = (j); i<(k); i++)
#define ROF(i,j,k) for(auto i = (k)-1; i>=(j); i--)
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define pb push_back
#define BOOST ios_base::sync_with_stdio(0);cin.tie(0);

const int MN = 21;
const int MM = 2e5+10;
const ll inf = 1e18+2;

vi V;
void gen(int mask, int n)
{
	bitset<MN> M = mask;
	int i = 0;
	while(i<n)
	{
		int j = i;
		while(M[j]) j++;
		V.pb(j);
		ROF(k,i,j) V.pb(k);
		i = j+1;
	}
}

int c(int n, vi C)//koszt uzyskania V z C
{
	int rep = 0;
	FOR(i,0,n)
	{
		int k = V[i];
		int p = i;
		while(C[p] != k) p++;
		while(p>i)
		{
			swap(C[p],C[p-1]);
			p--;
			rep++;
		}
	}
	return rep;
}


int main()
{
	int n;
	cin>>n;
	vi C(n);
	FOR(i,0,n)
	{
		cin>>C[i];
		C[i]--;
	}
	int ans = 1e9+7;
	FOR(m,0,1<<(n-1))
	{
		V.clear();
		gen(m,n);
		ans = min(c(n,C),ans);
	}
	cout<<ans;
}

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