Submission #889813

#	Time	Username	Problem	Language	Result	Execution time	Memory
889813		vjudge1	Chorus (JOI23_chorus)	C++17	16 / 100	5675 ms	1048576 KiB

chorus

/*
author : abushbandit
*/

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast,unroll-loops")

using namespace __gnu_pbds;
using namespace std;

#define int long long
#define pb push_back

const int N = 1e5 + 1,INF = 1e18;
 
void solve(){
	
	int n,m;
	cin >> n >> m;
	string s;
	cin >> s;
	
	map<string,int> dis;
	string h = s;
	sort(h.begin(),h.end());
	
	dis[s] = 1;
	
	queue<string> q;
	q.push(s);
	int ans = INF;
	n = s.size();
	
	while(!q.empty()){	
		s = q.front();
		q.pop();
	
		int cnt = 0;
		vector<int> vis(n);
		bool check = 1;
		
		for(int i = n - 1;i >= 0;i--){
			if(vis[i]) continue;
			if(s[i] == 'A'){
				check = 0;
				break;
			}
			cnt++;
			int u = 1;
			for(int j = i - 1;j >= 0;j--){
				if(vis[j])continue;
				if(s[j] == 'A'){
					break;
				}
				
				u++;
				vis[j] = 1;
			}
			for(int j = i - 1;j >= 0;j--){
				if(vis[j]){
					continue; 
				}
				if(s[j] == 'A'){
					u--;
					vis[j] = 1;
				}
				if(u == 0){
					break;
				}
			}
			
			if(u != 0){
				check = 0;
				break;
			}
		}
		if(m == cnt && check){
			ans = min(ans,dis[s] - 1);
		}
		h = s;
		for(int i = 0;i < n - 1;i++){
			swap(s[i],s[i + 1]);
			if(dis[s] > dis[h] + 1 || dis[s] == 0){	
				dis[s] = dis[h] + 1;
				q.push(s);
			}
			swap(s[i],s[i + 1]);
		}
		
	}
	cout << ans << "\n";
 
}
 
signed main() {
	
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int t = 1;
//	cin >> t;
	while(t--){
		solve();
	}
 
}

• Subtask 1: 16 / 16
• Subtask 2: 0 / 24
• Subtask 3: 0 / 21
• Subtask 4: 0 / 26
• Subtask 5: 0 / 13