oj.uz

Submission #889726

# Submission time Handle Problem Language Result Execution time Memory
889726 2023-12-20T06:20:11 Z vjudge1 Chorus (JOI23_chorus) C++17
16 / 100
 1544 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));
	do{
		dist[rts] = mod;
	}while(next_permutation(all(rts)));
	
	dist[str] = 0;
	
	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]);
			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] = 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 995 ms 21220 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 10 ms 600 KB Output is correct
7 Correct 1016 ms 21656 KB Output is correct
8 Correct 1031 ms 21628 KB Output is correct
9 Correct 1012 ms 21280 KB Output is correct
10 Correct 1002 ms 21036 KB Output is correct
11 Correct 1040 ms 21248 KB Output is correct
12 Correct 1022 ms 21072 KB Output is correct
13 Correct 61 ms 20556 KB Output is correct
14 Correct 1014 ms 21388 KB Output is correct
15 Correct 991 ms 21464 KB Output is correct
16 Correct 991 ms 21584 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 995 ms 21220 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 10 ms 600 KB Output is correct
7 Correct 1016 ms 21656 KB Output is correct
8 Correct 1031 ms 21628 KB Output is correct
9 Correct 1012 ms 21280 KB Output is correct
10 Correct 1002 ms 21036 KB Output is correct
11 Correct 1040 ms 21248 KB Output is correct
12 Correct 1022 ms 21072 KB Output is correct
13 Correct 61 ms 20556 KB Output is correct
14 Correct 1014 ms 21388 KB Output is correct
15 Correct 991 ms 21464 KB Output is correct
16 Correct 991 ms 21584 KB Output is correct
17 Runtime error 1544 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 995 ms 21220 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 10 ms 600 KB Output is correct
7 Correct 1016 ms 21656 KB Output is correct
8 Correct 1031 ms 21628 KB Output is correct
9 Correct 1012 ms 21280 KB Output is correct
10 Correct 1002 ms 21036 KB Output is correct
11 Correct 1040 ms 21248 KB Output is correct
12 Correct 1022 ms 21072 KB Output is correct
13 Correct 61 ms 20556 KB Output is correct
14 Correct 1014 ms 21388 KB Output is correct
15 Correct 991 ms 21464 KB Output is correct
16 Correct 991 ms 21584 KB Output is correct
17 Runtime error 1544 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 995 ms 21220 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 10 ms 600 KB Output is correct
7 Correct 1016 ms 21656 KB Output is correct
8 Correct 1031 ms 21628 KB Output is correct
9 Correct 1012 ms 21280 KB Output is correct
10 Correct 1002 ms 21036 KB Output is correct
11 Correct 1040 ms 21248 KB Output is correct
12 Correct 1022 ms 21072 KB Output is correct
13 Correct 61 ms 20556 KB Output is correct
14 Correct 1014 ms 21388 KB Output is correct
15 Correct 991 ms 21464 KB Output is correct
16 Correct 991 ms 21584 KB Output is correct
17 Runtime error 1544 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 995 ms 21220 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 10 ms 600 KB Output is correct
7 Correct 1016 ms 21656 KB Output is correct
8 Correct 1031 ms 21628 KB Output is correct
9 Correct 1012 ms 21280 KB Output is correct
10 Correct 1002 ms 21036 KB Output is correct
11 Correct 1040 ms 21248 KB Output is correct
12 Correct 1022 ms 21072 KB Output is correct
13 Correct 61 ms 20556 KB Output is correct
14 Correct 1014 ms 21388 KB Output is correct
15 Correct 991 ms 21464 KB Output is correct
16 Correct 991 ms 21584 KB Output is correct
17 Runtime error 1544 ms 1048576 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -