oj.uz

Submission #954357

# Submission time Handle Problem Language Result Execution time Memory
954357 2024-03-27T16:34:38 Z LCJLY Building 4 (JOI20_building4) C++14
11 / 100
 586 ms 346672 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<pii,pii>pi2;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
 
int n;
int a[1000005];
int b[1000005];
int memo[4005][2005][2];
array<int,3>pp[4005][4005][2];

//a is true, b is false

int dp(int index, int take, bool amos){
	if(index==2*n){
		if(take==n){
			return true;
		}
		else return false;
	}
	if(memo[index][take][amos]!=-1) return memo[index][take][amos];
	bool ans=false;
	if(index==0){
		bool hold=dp(index+1,take+1,true);
		if(hold) pp[index][take][amos]={index+1,take+1,true};
		ans|=hold;
		
		hold=dp(index+1,take,false);
		if(hold) pp[index][take][amos]={index+1,take,false};
		ans|=hold;
	}
	else if(amos){
		if(a[index]>=a[index-1]){
			//ans|=dp(index+1,take+1,true);
			bool hold=dp(index+1,take+1,true);
			if(hold) pp[index][take][amos]={index+1,take+1,true};
			ans|=hold;
		}
		if(b[index]>=a[index-1]){
			//ans|=dp(index+1,take,false);
			bool hold=dp(index+1,take,false);
			if(hold) pp[index][take][amos]={index+1,take,false};
			ans|=hold;
		}
	}
	else{
		if(a[index]>=b[index-1]){
			//ans|=dp(index+1,take+1,true);
			bool hold=dp(index+1,take+1,true);
			if(hold) pp[index][take][amos]={index+1,take+1,true};
			ans|=hold;
		}
		if(b[index]>=b[index-1]){
			//ans|=dp(index+1,take,false);
			bool hold=dp(index+1,take,false);
			if(hold) pp[index][take][amos]={index+1,take,false};
			ans|=hold;
		}
	}
	return memo[index][take][amos]=(int)ans;
}
 
void solve(){
	cin >> n;
	
	for(int x=0;x<2*n;x++){
		cin >> a[x];
	}
	
	for(int x=0;x<2*n;x++){
		cin >> b[x];
	}
	
	memset(memo,-1,sizeof(memo));
	bool hold=dp(0,0,0);
	if(!hold){
		cout << -1;
		return;
	}
	
	array<int,3>cur;
	cur={0,0,0};
	
	while(cur[0]<2*n){
		array<int,3>nxt=pp[cur[0]][cur[1]][cur[2]];
		if(nxt[2]==1){
			cout << "A";
		}
		else cout << "B";
		cur=nxt;
	}
}	
 
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 129616 KB Output is correct
2 Correct 18 ms 129620 KB Output is correct
3 Correct 19 ms 129624 KB Output is correct
4 Correct 18 ms 129632 KB Output is correct
5 Correct 18 ms 129628 KB Output is correct
6 Correct 25 ms 146004 KB Output is correct
7 Correct 25 ms 144068 KB Output is correct
8 Correct 346 ms 283920 KB Output is correct
9 Correct 110 ms 153412 KB Output is correct
10 Correct 111 ms 149792 KB Output is correct
11 Correct 24 ms 152400 KB Output is correct
12 Correct 27 ms 153692 KB Output is correct
13 Correct 24 ms 155740 KB Output is correct
14 Correct 586 ms 346672 KB Output is correct
15 Correct 121 ms 157524 KB Output is correct
16 Correct 131 ms 130336 KB Output is correct
17 Correct 305 ms 208728 KB Output is correct
18 Correct 26 ms 157712 KB Output is correct
19 Correct 26 ms 157784 KB Output is correct
20 Correct 26 ms 157528 KB Output is correct
21 Correct 30 ms 157524 KB Output is correct
22 Correct 523 ms 343904 KB Output is correct
23 Correct 338 ms 274768 KB Output is correct
24 Correct 466 ms 345348 KB Output is correct
25 Correct 212 ms 173088 KB Output is correct
26 Correct 192 ms 170340 KB Output is correct
27 Correct 183 ms 157520 KB Output is correct
28 Correct 125 ms 178492 KB Output is correct
29 Correct 143 ms 186448 KB Output is correct
30 Correct 97 ms 164652 KB Output is correct
31 Correct 124 ms 164956 KB Output is correct
32 Correct 78 ms 152592 KB Output is correct
33 Correct 106 ms 154196 KB Output is correct

Subtask #2
0 / 89.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 129616 KB Output is correct
2 Correct 18 ms 129620 KB Output is correct
3 Correct 19 ms 129624 KB Output is correct
4 Correct 18 ms 129632 KB Output is correct
5 Correct 18 ms 129628 KB Output is correct
6 Correct 25 ms 146004 KB Output is correct
7 Correct 25 ms 144068 KB Output is correct
8 Correct 346 ms 283920 KB Output is correct
9 Correct 110 ms 153412 KB Output is correct
10 Correct 111 ms 149792 KB Output is correct
11 Correct 24 ms 152400 KB Output is correct
12 Correct 27 ms 153692 KB Output is correct
13 Correct 24 ms 155740 KB Output is correct
14 Correct 586 ms 346672 KB Output is correct
15 Correct 121 ms 157524 KB Output is correct
16 Correct 131 ms 130336 KB Output is correct
17 Correct 305 ms 208728 KB Output is correct
18 Correct 26 ms 157712 KB Output is correct
19 Correct 26 ms 157784 KB Output is correct
20 Correct 26 ms 157528 KB Output is correct
21 Correct 30 ms 157524 KB Output is correct
22 Correct 523 ms 343904 KB Output is correct
23 Correct 338 ms 274768 KB Output is correct
24 Correct 466 ms 345348 KB Output is correct
25 Correct 212 ms 173088 KB Output is correct
26 Correct 192 ms 170340 KB Output is correct
27 Correct 183 ms 157520 KB Output is correct
28 Correct 125 ms 178492 KB Output is correct
29 Correct 143 ms 186448 KB Output is correct
30 Correct 97 ms 164652 KB Output is correct
31 Correct 124 ms 164956 KB Output is correct
32 Correct 78 ms 152592 KB Output is correct
33 Correct 106 ms 154196 KB Output is correct
34 Correct 173 ms 160596 KB Output is correct
35 Incorrect 163 ms 177036 KB Output isn't correct
36 Halted 0 ms 0 KB -