Submission #424609

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
424609	2021-06-12T07:40:58 Z	amunduzbaev	Building 4 (JOI20_building4)	C++14	11 / 100	2000 ms	377740 KB

building4

/* made by amunduzbaev */
 
//~ #include <ext/pb_ds/assoc_container.hpp>
//~ #include <ext/pb_ds/tree_policy.hpp>
#include "bits/stdc++.h"
 
using namespace std;
//~ using namespace __gnu_pbds;

#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define NeedForSpeed ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define vv vector
#define mem(arr, v) memset(arr, v, sizeof arr)
#define int long long
#define degub(x) cout<<#x<<" : "<<x<<"\n"
#define GG cout<<"here\n";
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii; 
typedef vector<int> vii;
typedef vector<pii> vpii;
template<class T> bool umin(T& a, const T& b) { return a > b ? a = b, true : false; }
template<class T> bool umax(T& a, const T& b) { return a < b ? a = b, true : false; }
template<int sz> using tut = array<int, sz>;
void usaco(string s) { freopen((s+".in").c_str(),"r",stdin);  
	freopen((s+".out").c_str(),"w",stdout); NeedForSpeed }
//~ template<class T> using oset = tree<T, 
//~ null_type, less_equal<T>, rb_tree_tag, 
//~ tree_order_statistics_node_update> ordered_set;
 
const int N = 4e3+5;
const int mod = 1e9+7;
const ll inf = 1e18;
const ld Pi = acos(-1);
 
#define MULTI 0
int n, m, k, s, t, q, ans, res, a[N];
int dp[N][N][2], b[N];
pii par[N][N][2];

void solve(int t_case){
	cin>>n, m = 2 * n;
	for(int i=1;i<=m;i++) cin>>a[i];
	for(int i=1;i<=m;i++) cin>>b[i];
	for(int i=0;i<=m;i++) for(int j=0;j<=n;j++) par[i][j][0] = par[i][j][1] = {-1, -1};
	
	dp[0][0][0] = dp[0][0][1] = 1;
	
	for(int i=1;i<=m;i++){
		if(i <= n && a[i] >= a[i-1] && dp[i-1][i-1][0]) dp[i][i][0] |= 1, par[i][i][0] = {i-1, 0};
		if(i <= n && b[i] >= b[i-1] && dp[i-1][0][1]) dp[i][0][1] = 1, par[i][0][1] = {0, 1};
		for(int j=1;j<min(i, n + 1);j++){
			// if i, j, 0 is j A's  i-j B's and last is A
			if(a[i] >= a[i-1] && dp[i-1][j-1][0]) dp[i][j][0] |= 1, par[i][j][0] = {j-1, 0};
			if(a[i] >= b[i-1] && dp[i-1][j-1][1]) dp[i][j][0] |= 1, par[i][j][0] = {j-1, 1};
			// if i, j, 1 is j A's  i-j B's and last is B
			if(b[i] >= a[i-1] && dp[i-1][j][0]) dp[i][j][1] |= 1, par[i][j][1] = {j, 0};
			if(b[i] >= b[i-1] && dp[i-1][j][1]) dp[i][j][1] |= 1, par[i][j][1] = {j, 1};
		}
	} 
	
	cout<<"\n";
	//~ for(int i=0;i<=n;i++){
		//~ for(int j=0;j<=m;j++) cout<<dp[j][i][0]<<" ";
		//~ cout<<"\n";
	//~ } cout<<"\n";
	
	//~ for(int i=0;i<=n;i++){
		//~ for(int j=0;j<=m;j++) cout<<dp[j][i][1]<<" ";
		//~ cout<<"\n";
	//~ } cout<<"\n";
	
	int i = m, j = n, t = 0;
	if(dp[m][n][0]) t = 0;
	else if(dp[m][n][1]) t = 1;
	else { cout<<"-1\n"; return; }
	vii tt;
	
	while(i){ tt.pb(t);
		pii pp = par[i][j][t];
		j = pp.ff, t = pp.ss, i--;
	} 
	reverse(all(tt));
	for(auto x : tt){
		if(x) cout<<"B";
		else cout<<"A";
	} cout<<"\n";
}

signed main(){
	NeedForSpeed
	if(MULTI){
		int t; cin>>t;
		for(int t_case = 1; t_case <= t; t_case++) solve(t_case);
	} else solve(1);
	return 0;
}

Compilation message

building4.cpp: In function 'void usaco(std::string)':
building4.cpp:34:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 | void usaco(string s) { freopen((s+".in").c_str(),"r",stdin);
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
building4.cpp:35:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |  freopen((s+".out").c_str(),"w",stdout); NeedForSpeed }
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	144 ms	229804 KB	Output is correct
6	Correct	147 ms	233068 KB	Output is correct
7	Correct	125 ms	186028 KB	Output is correct
8	Correct	175 ms	282348 KB	Output is correct
9	Correct	159 ms	271300 KB	Output is correct
10	Correct	135 ms	219916 KB	Output is correct
11	Correct	183 ms	251892 KB	Output is correct
12	Correct	226 ms	284276 KB	Output is correct
13	Correct	177 ms	284076 KB	Output is correct
14	Correct	228 ms	377740 KB	Output is correct
15	Correct	199 ms	346536 KB	Output is correct
16	Correct	188 ms	315204 KB	Output is correct
17	Correct	197 ms	334704 KB	Output is correct
18	Correct	205 ms	284052 KB	Output is correct
19	Correct	178 ms	284036 KB	Output is correct
20	Correct	174 ms	284192 KB	Output is correct
21	Correct	180 ms	284080 KB	Output is correct
22	Correct	224 ms	377156 KB	Output is correct
23	Correct	203 ms	343884 KB	Output is correct
24	Correct	216 ms	377672 KB	Output is correct
25	Correct	187 ms	329016 KB	Output is correct
26	Correct	196 ms	332000 KB	Output is correct
27	Correct	205 ms	377664 KB	Output is correct
28	Correct	155 ms	255556 KB	Output is correct
29	Correct	197 ms	317216 KB	Output is correct
30	Correct	165 ms	254396 KB	Output is correct
31	Correct	185 ms	311236 KB	Output is correct
32	Correct	138 ms	222400 KB	Output is correct
33	Correct	188 ms	312672 KB	Output is correct

Subtask #2

0 / 89.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	144 ms	229804 KB	Output is correct
6	Correct	147 ms	233068 KB	Output is correct
7	Correct	125 ms	186028 KB	Output is correct
8	Correct	175 ms	282348 KB	Output is correct
9	Correct	159 ms	271300 KB	Output is correct
10	Correct	135 ms	219916 KB	Output is correct
11	Correct	183 ms	251892 KB	Output is correct
12	Correct	226 ms	284276 KB	Output is correct
13	Correct	177 ms	284076 KB	Output is correct
14	Correct	228 ms	377740 KB	Output is correct
15	Correct	199 ms	346536 KB	Output is correct
16	Correct	188 ms	315204 KB	Output is correct
17	Correct	197 ms	334704 KB	Output is correct
18	Correct	205 ms	284052 KB	Output is correct
19	Correct	178 ms	284036 KB	Output is correct
20	Correct	174 ms	284192 KB	Output is correct
21	Correct	180 ms	284080 KB	Output is correct
22	Correct	224 ms	377156 KB	Output is correct
23	Correct	203 ms	343884 KB	Output is correct
24	Correct	216 ms	377672 KB	Output is correct
25	Correct	187 ms	329016 KB	Output is correct
26	Correct	196 ms	332000 KB	Output is correct
27	Correct	205 ms	377664 KB	Output is correct
28	Correct	155 ms	255556 KB	Output is correct
29	Correct	197 ms	317216 KB	Output is correct
30	Correct	165 ms	254396 KB	Output is correct
31	Correct	185 ms	311236 KB	Output is correct
32	Correct	138 ms	222400 KB	Output is correct
33	Correct	188 ms	312672 KB	Output is correct
34	Execution timed out	2065 ms	332 KB	Time limit exceeded
35	Halted	0 ms	0 KB	-