oj.uz

Submission #920623

# Submission time Handle Problem Language Result Execution time Memory
920623 2024-02-02T19:48:47 Z alexander707070 Building 4 (JOI20_building4) C++14
11 / 100
 51 ms 16840 KB 
#include<bits/stdc++.h>
#define MAXN 500007
using namespace std;

const int inf=1e9;

int n,a[MAXN],b[MAXN],cnt,p[MAXN],l,r;
int dp[MAXN][2],dp2[MAXN][2];
bool li[MAXN][2],li2[MAXN][2];

queue<int> s;

string sol,sol2;

int ff(int pos,int last){
	if(pos==n+1)return 0;

	if(li[pos][last])return dp[pos][last];
	li[pos][last]=true;
	dp[pos][last]=-inf;

	int x=0;
	if(last==0)x=a[pos-1];
	else x=b[pos-1];

	if(a[pos]>=x){
		dp[pos][last]=max(dp[pos][last],ff(pos+1,0)+1);
	}

	if(b[pos]>=x){
		dp[pos][last]=max(dp[pos][last],ff(pos+1,1));
	}

	return dp[pos][last];
}

int ff2(int pos,int last){
	if(pos==n+1)return 0;

	if(li2[pos][last])return dp2[pos][last];
	li2[pos][last]=true;
	dp2[pos][last]=-inf;

	int x=0;
	if(last==0)x=a[pos-1];
	else x=b[pos-1];

	if(a[pos]>=x){
		dp2[pos][last]=max(dp2[pos][last],ff2(pos+1,0));
	}

	if(b[pos]>=x){
		dp2[pos][last]=max(dp2[pos][last],ff2(pos+1,1)+1);
	}

	return dp2[pos][last];
}

void solve(int pos,int last){
	if(pos==n+1)return;

	int x;
	if(last==0)x=a[pos-1];
	else x=b[pos-1];

	if(a[pos]>=x and ff(pos,last)==ff(pos+1,0)+1){
		sol+="A"; solve(pos+1,0); return;
	}else{
		sol+="B"; solve(pos+1,1); return;
	}
}

void solve2(int pos,int last){
	if(pos==n+1)return;

	int x;
	if(last==0)x=a[pos-1];
	else x=b[pos-1];

	if(b[pos]>=x and ff2(pos,last)==ff2(pos+1,1)+1){
		sol2+="B"; solve2(pos+1,1); return;
	}else{
		sol2+="A"; solve2(pos+1,0); return;
	}
}

bool vis[MAXN];

void bfs(int pos){

	if(pos>0 and !vis[pos-1] and sol[pos-1]=='A' and sol2[pos-1]=='B'){
		l=pos-1;
		if(b[l+1]>=p[l] and b[l+1]<=p[l+2]){
			s.push(pos-1);
			vis[pos-1]=true;
		}
	}

	if(pos<n-1 and !vis[pos+1] and sol[pos+1]=='A' and sol2[pos+1]=='B'){
		l=pos+1;
		if(b[l+1]>=p[l] and b[l+1]<=p[l+2]){
			s.push(pos+1);
			vis[pos+1]=true;
		}
	}
}

int main(){

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin>>n;
	n*=2;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		cin>>b[i];
	}

	if(ff(1,0)<0 or ff(1,0)<n/2 or ff2(1,0)<n/2){
		cout<<"-1\n";
		return 0;
	}

	cnt=ff(1,0);
	solve(1,0); solve2(1,0);

	for(int i=0;i<sol.size();i++){
		if(sol[i]=='A')p[i+1]=a[i+1];
		else p[i+1]=b[i+1];
	}
	p[n+1]=inf;

	for(int i=0;i<sol.size();i++){
		if(sol[i]=='A' and sol2[i]=='B'){
			if(b[i+1]>=p[i] and b[i+1]<=p[i+2]){
				s.push(i); vis[i]=true;
			}
		}
	}

	while(cnt>n/2 and !s.empty()){
		sol[s.front()]='B'; 
		p[s.front()+1]=b[s.front()+1];

		bfs(s.front());
		s.pop();

		cnt--;
	}

	cout<<sol<<"\n";
	

	return 0;
}

Compilation message

building4.cpp: In function 'int main()':
building4.cpp:131:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |  for(int i=0;i<sol.size();i++){
      |              ~^~~~~~~~~~~
building4.cpp:137:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |  for(int i=0;i<sol.size();i++){
      |              ~^~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 12632 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 8740 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 3 ms 12892 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 3 ms 12892 KB Output is correct
12 Correct 3 ms 12892 KB Output is correct
13 Correct 3 ms 12892 KB Output is correct
14 Correct 3 ms 13028 KB Output is correct
15 Correct 3 ms 13100 KB Output is correct
16 Correct 2 ms 10844 KB Output is correct
17 Correct 3 ms 12888 KB Output is correct
18 Correct 3 ms 13144 KB Output is correct
19 Correct 3 ms 12888 KB Output is correct
20 Correct 3 ms 12888 KB Output is correct
21 Correct 3 ms 12892 KB Output is correct
22 Correct 2 ms 12892 KB Output is correct
23 Correct 3 ms 12892 KB Output is correct
24 Correct 3 ms 12888 KB Output is correct
25 Correct 2 ms 13148 KB Output is correct
26 Correct 3 ms 12892 KB Output is correct
27 Correct 3 ms 12892 KB Output is correct
28 Correct 2 ms 12892 KB Output is correct
29 Correct 3 ms 12892 KB Output is correct
30 Correct 3 ms 12804 KB Output is correct
31 Correct 3 ms 12892 KB Output is correct
32 Correct 3 ms 12892 KB Output is correct
33 Correct 3 ms 13048 KB Output is correct

Subtask #2
0 / 89.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 12632 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 8740 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 3 ms 12892 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 3 ms 12892 KB Output is correct
12 Correct 3 ms 12892 KB Output is correct
13 Correct 3 ms 12892 KB Output is correct
14 Correct 3 ms 13028 KB Output is correct
15 Correct 3 ms 13100 KB Output is correct
16 Correct 2 ms 10844 KB Output is correct
17 Correct 3 ms 12888 KB Output is correct
18 Correct 3 ms 13144 KB Output is correct
19 Correct 3 ms 12888 KB Output is correct
20 Correct 3 ms 12888 KB Output is correct
21 Correct 3 ms 12892 KB Output is correct
22 Correct 2 ms 12892 KB Output is correct
23 Correct 3 ms 12892 KB Output is correct
24 Correct 3 ms 12888 KB Output is correct
25 Correct 2 ms 13148 KB Output is correct
26 Correct 3 ms 12892 KB Output is correct
27 Correct 3 ms 12892 KB Output is correct
28 Correct 2 ms 12892 KB Output is correct
29 Correct 3 ms 12892 KB Output is correct
30 Correct 3 ms 12804 KB Output is correct
31 Correct 3 ms 12892 KB Output is correct
32 Correct 3 ms 12892 KB Output is correct
33 Correct 3 ms 13048 KB Output is correct
34 Runtime error 51 ms 16840 KB Execution killed with signal 11
35 Halted 0 ms 0 KB -