Submission #889813

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
889813	2023-12-20T07:26:32 Z	vjudge1	Chorus (JOI23_chorus)	C++17	16 / 100	5675 ms	1048576 KB

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.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	600 KB	Output is correct
4	Correct	1185 ms	20752 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	13 ms	860 KB	Output is correct
7	Correct	1265 ms	20668 KB	Output is correct
8	Correct	1216 ms	20688 KB	Output is correct
9	Correct	1183 ms	20724 KB	Output is correct
10	Correct	1206 ms	20704 KB	Output is correct
11	Correct	1205 ms	20512 KB	Output is correct
12	Correct	1176 ms	20928 KB	Output is correct
13	Correct	1214 ms	20632 KB	Output is correct
14	Correct	1188 ms	20720 KB	Output is correct
15	Correct	1203 ms	20908 KB	Output is correct
16	Correct	1183 ms	20708 KB	Output is correct

Subtask #2

0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	600 KB	Output is correct
4	Correct	1185 ms	20752 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	13 ms	860 KB	Output is correct
7	Correct	1265 ms	20668 KB	Output is correct
8	Correct	1216 ms	20688 KB	Output is correct
9	Correct	1183 ms	20724 KB	Output is correct
10	Correct	1206 ms	20704 KB	Output is correct
11	Correct	1205 ms	20512 KB	Output is correct
12	Correct	1176 ms	20928 KB	Output is correct
13	Correct	1214 ms	20632 KB	Output is correct
14	Correct	1188 ms	20720 KB	Output is correct
15	Correct	1203 ms	20908 KB	Output is correct
16	Correct	1183 ms	20708 KB	Output is correct
17	Runtime error	5675 ms	1048576 KB	Execution killed with signal 9
18	Halted	0 ms	0 KB	-

Subtask #3

0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	600 KB	Output is correct
4	Correct	1185 ms	20752 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	13 ms	860 KB	Output is correct
7	Correct	1265 ms	20668 KB	Output is correct
8	Correct	1216 ms	20688 KB	Output is correct
9	Correct	1183 ms	20724 KB	Output is correct
10	Correct	1206 ms	20704 KB	Output is correct
11	Correct	1205 ms	20512 KB	Output is correct
12	Correct	1176 ms	20928 KB	Output is correct
13	Correct	1214 ms	20632 KB	Output is correct
14	Correct	1188 ms	20720 KB	Output is correct
15	Correct	1203 ms	20908 KB	Output is correct
16	Correct	1183 ms	20708 KB	Output is correct
17	Runtime error	5675 ms	1048576 KB	Execution killed with signal 9
18	Halted	0 ms	0 KB	-

Subtask #4

0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	600 KB	Output is correct
4	Correct	1185 ms	20752 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	13 ms	860 KB	Output is correct
7	Correct	1265 ms	20668 KB	Output is correct
8	Correct	1216 ms	20688 KB	Output is correct
9	Correct	1183 ms	20724 KB	Output is correct
10	Correct	1206 ms	20704 KB	Output is correct
11	Correct	1205 ms	20512 KB	Output is correct
12	Correct	1176 ms	20928 KB	Output is correct
13	Correct	1214 ms	20632 KB	Output is correct
14	Correct	1188 ms	20720 KB	Output is correct
15	Correct	1203 ms	20908 KB	Output is correct
16	Correct	1183 ms	20708 KB	Output is correct
17	Runtime error	5675 ms	1048576 KB	Execution killed with signal 9
18	Halted	0 ms	0 KB	-

Subtask #5

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	600 KB	Output is correct
4	Correct	1185 ms	20752 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	13 ms	860 KB	Output is correct
7	Correct	1265 ms	20668 KB	Output is correct
8	Correct	1216 ms	20688 KB	Output is correct
9	Correct	1183 ms	20724 KB	Output is correct
10	Correct	1206 ms	20704 KB	Output is correct
11	Correct	1205 ms	20512 KB	Output is correct
12	Correct	1176 ms	20928 KB	Output is correct
13	Correct	1214 ms	20632 KB	Output is correct
14	Correct	1188 ms	20720 KB	Output is correct
15	Correct	1203 ms	20908 KB	Output is correct
16	Correct	1183 ms	20708 KB	Output is correct
17	Runtime error	5675 ms	1048576 KB	Execution killed with signal 9
18	Halted	0 ms	0 KB	-