oj.uz

Submission #889731

# Submission time Handle Problem Language Result Execution time Memory
889731 2023-12-20T06:23:59 Z vjudge1 Chorus (JOI23_chorus) C++17
16 / 100
 6076 ms 1048576 KB 
#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")
#define pii pair<int,int>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long
#define f first
#define s second
#define pii pair<int,int>
template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;}
typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
	tree_order_statistics_node_update> ordered_set;
const int mod= 1e9 +7;
const int N=1e5*4;

int binpow (int a, int n) {
	if (n == 0)
		return 1;
	if (n % 2 == 1)
		return binpow (a, n-1) * a;
	else {
		int b = binpow (a, n/2);
		return b * b;
	}
}

void solve(){
	
	int n,m,k;
	cin>>n>>m;
	string str;
	cin>>str;
	
	map<string,int>dist;
	string rts = str;
	sort(all(rts));
	
	dist[str] = 1;
	
	queue<string>q;
	q.push(str);
	int ans = mod;
	n = str.size();
	
	while(!q.empty()){	
		str = q.front();
		q.pop();
	
		int cnt = 0;
		vector<int>vis(n);
		bool flag = true;
		
		for(int i = n-1;i>=0;i--){
			if(vis[i])continue;
			if(str[i]=='A'){
				flag = false;
				break;
			}
			cnt++;
			int u = 1;
			for(int j = i - 1;j>=0;j--){
				if(vis[j])continue;
				if(str[j]=='A')break;
				
				u++;
				vis[j] = 1;
			}
			for(int j = i - 1;j>=0;j--){
				if(vis[j])continue;
				if(str[j]=='A'){
					u--;
					vis[j] = 1;
				}
				if(u==0)break;
			}
			
			if(u!=0){
				flag = false;
				break;
			}
			
		}
		if(m==cnt&&flag){
			umin(ans,dist[str] - 1);
			continue;
		}
		rts = str;
		for(int i = 0;i<n-1;i++){
			swap(str[i],str[i+1]);
			if(dist[str]>dist[rts]+1||dist[str]==0){	
				dist[str] = dist[rts] + 1;
				q.push(str);
			}
			swap(str[i],str[i+1]);
		}
		
	}
	cout<<ans<<"\n";
	
	







}

 signed main()
{
//	freopen("seq.in", "r", stdin);
//  freopen("seq.out", "w", stdout);
	ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
	int tt=1;//cin>>tt;
	while(tt--)solve();

}

Compilation message

chorus.cpp: In function 'void solve()':
chorus.cpp:36:10: warning: unused variable 'k' [-Wunused-variable]
   36 |  int n,m,k;
      |          ^

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1307 ms 20536 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 13 ms 600 KB Output is correct
7 Correct 1350 ms 20648 KB Output is correct
8 Correct 1352 ms 20676 KB Output is correct
9 Correct 1348 ms 20700 KB Output is correct
10 Correct 1367 ms 20636 KB Output is correct
11 Correct 1346 ms 20456 KB Output is correct
12 Correct 1342 ms 20532 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1378 ms 20484 KB Output is correct
15 Correct 1321 ms 20592 KB Output is correct
16 Correct 1327 ms 20676 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1307 ms 20536 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 13 ms 600 KB Output is correct
7 Correct 1350 ms 20648 KB Output is correct
8 Correct 1352 ms 20676 KB Output is correct
9 Correct 1348 ms 20700 KB Output is correct
10 Correct 1367 ms 20636 KB Output is correct
11 Correct 1346 ms 20456 KB Output is correct
12 Correct 1342 ms 20532 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1378 ms 20484 KB Output is correct
15 Correct 1321 ms 20592 KB Output is correct
16 Correct 1327 ms 20676 KB Output is correct
17 Runtime error 6076 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 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1307 ms 20536 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 13 ms 600 KB Output is correct
7 Correct 1350 ms 20648 KB Output is correct
8 Correct 1352 ms 20676 KB Output is correct
9 Correct 1348 ms 20700 KB Output is correct
10 Correct 1367 ms 20636 KB Output is correct
11 Correct 1346 ms 20456 KB Output is correct
12 Correct 1342 ms 20532 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1378 ms 20484 KB Output is correct
15 Correct 1321 ms 20592 KB Output is correct
16 Correct 1327 ms 20676 KB Output is correct
17 Runtime error 6076 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 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1307 ms 20536 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 13 ms 600 KB Output is correct
7 Correct 1350 ms 20648 KB Output is correct
8 Correct 1352 ms 20676 KB Output is correct
9 Correct 1348 ms 20700 KB Output is correct
10 Correct 1367 ms 20636 KB Output is correct
11 Correct 1346 ms 20456 KB Output is correct
12 Correct 1342 ms 20532 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1378 ms 20484 KB Output is correct
15 Correct 1321 ms 20592 KB Output is correct
16 Correct 1327 ms 20676 KB Output is correct
17 Runtime error 6076 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 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1307 ms 20536 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 13 ms 600 KB Output is correct
7 Correct 1350 ms 20648 KB Output is correct
8 Correct 1352 ms 20676 KB Output is correct
9 Correct 1348 ms 20700 KB Output is correct
10 Correct 1367 ms 20636 KB Output is correct
11 Correct 1346 ms 20456 KB Output is correct
12 Correct 1342 ms 20532 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1378 ms 20484 KB Output is correct
15 Correct 1321 ms 20592 KB Output is correct
16 Correct 1327 ms 20676 KB Output is correct
17 Runtime error 6076 ms 1048576 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -