oj.uz

Submission #889732

# Submission time Handle Problem Language Result Execution time Memory
889732 2023-12-20T06:24:50 Z Minbaev Chorus (JOI23_chorus) C++17
16 / 100
 6170 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 348 KB Output is correct
2 Correct 1 ms 360 KB Output is correct
3 Correct 1 ms 452 KB Output is correct
4 Correct 1341 ms 20516 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 14 ms 604 KB Output is correct
7 Correct 1352 ms 20736 KB Output is correct
8 Correct 1361 ms 20592 KB Output is correct
9 Correct 1334 ms 20632 KB Output is correct
10 Correct 1339 ms 20496 KB Output is correct
11 Correct 1336 ms 20504 KB Output is correct
12 Correct 1342 ms 20656 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1373 ms 20644 KB Output is correct
15 Correct 1331 ms 20620 KB Output is correct
16 Correct 1338 ms 20548 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 360 KB Output is correct
3 Correct 1 ms 452 KB Output is correct
4 Correct 1341 ms 20516 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 14 ms 604 KB Output is correct
7 Correct 1352 ms 20736 KB Output is correct
8 Correct 1361 ms 20592 KB Output is correct
9 Correct 1334 ms 20632 KB Output is correct
10 Correct 1339 ms 20496 KB Output is correct
11 Correct 1336 ms 20504 KB Output is correct
12 Correct 1342 ms 20656 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1373 ms 20644 KB Output is correct
15 Correct 1331 ms 20620 KB Output is correct
16 Correct 1338 ms 20548 KB Output is correct
17 Runtime error 6170 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 360 KB Output is correct
3 Correct 1 ms 452 KB Output is correct
4 Correct 1341 ms 20516 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 14 ms 604 KB Output is correct
7 Correct 1352 ms 20736 KB Output is correct
8 Correct 1361 ms 20592 KB Output is correct
9 Correct 1334 ms 20632 KB Output is correct
10 Correct 1339 ms 20496 KB Output is correct
11 Correct 1336 ms 20504 KB Output is correct
12 Correct 1342 ms 20656 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1373 ms 20644 KB Output is correct
15 Correct 1331 ms 20620 KB Output is correct
16 Correct 1338 ms 20548 KB Output is correct
17 Runtime error 6170 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 360 KB Output is correct
3 Correct 1 ms 452 KB Output is correct
4 Correct 1341 ms 20516 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 14 ms 604 KB Output is correct
7 Correct 1352 ms 20736 KB Output is correct
8 Correct 1361 ms 20592 KB Output is correct
9 Correct 1334 ms 20632 KB Output is correct
10 Correct 1339 ms 20496 KB Output is correct
11 Correct 1336 ms 20504 KB Output is correct
12 Correct 1342 ms 20656 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1373 ms 20644 KB Output is correct
15 Correct 1331 ms 20620 KB Output is correct
16 Correct 1338 ms 20548 KB Output is correct
17 Runtime error 6170 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 360 KB Output is correct
3 Correct 1 ms 452 KB Output is correct
4 Correct 1341 ms 20516 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 14 ms 604 KB Output is correct
7 Correct 1352 ms 20736 KB Output is correct
8 Correct 1361 ms 20592 KB Output is correct
9 Correct 1334 ms 20632 KB Output is correct
10 Correct 1339 ms 20496 KB Output is correct
11 Correct 1336 ms 20504 KB Output is correct
12 Correct 1342 ms 20656 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1373 ms 20644 KB Output is correct
15 Correct 1331 ms 20620 KB Output is correct
16 Correct 1338 ms 20548 KB Output is correct
17 Runtime error 6170 ms 1048576 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -