Submission #1165781

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165781		nguyn	Building 4 (JOI20_building4)	C++20	100 / 100	131 ms	26040 KiB

building4

#include <bits/stdc++.h>
using namespace std;

#define ll long long 
#define F first
#define S second
#define pb push_back 
#define pii pair<int,int>

const int N = 1e6 + 5;
const int inf = 2e9;

int n, a[N], b[N]; 
pii f[N][2];

signed main(){
    ios_base::sync_with_stdio(false) ; 
    cin.tie(0) ; cout.tie(0) ; 
    if (fopen("INP.INP" ,"r")) {
        freopen("INP.INP" ,"r" , stdin) ;
        freopen("OUT.OUT" , "w" , stdout) ;
    }
    cin >> n;
    for (int i = 1; i <= 2 * n; i++) {
    	cin >> a[i];
    }
    for (int i = 1; i <= 2 * n; i++) {
    	cin >> b[i]; 
    }
    f[1][0] = {0, 0};
    f[1][1] = {1, 1}; 
    for (int i = 2; i <= 2 * n; i++) {
    	f[i][0] = f[i][1] = {inf, -inf}; 
    	if (a[i] >= a[i - 1]) {
    		pii cur = f[i - 1][0]; 
    		f[i][0].F = min(f[i][0].F, cur.F); 
    		f[i][0].S = max(f[i][0].S, cur.S); 
    	}
    	if (a[i] >= b[i - 1]) {
    		pii cur = f[i - 1][1];
    		f[i][0].F = min(f[i][0].F, cur.F);
    		f[i][0].S = max(f[i][0].S, cur.S);  
    	}
    	if (b[i] >= a[i - 1]) {
    		pii cur = f[i - 1][0]; 
    		f[i][1].F = min(f[i][1].F, cur.F + 1);
    		f[i][1].S = max(f[i][1].S, cur.S + 1); 
    	}
    	if (b[i] >= b[i - 1]) {
    		pii cur = f[i - 1][1]; 
    		f[i][1].F = min(f[i][1].F, cur.F + 1);
    		f[i][1].S = max(f[i][1].S, cur.S + 1);
    	}
    }
    int last = -1; 
	// cout << f[n][0].F << ' ' << f[n][0].S << '\n'; 
	// cout << f[n][1].F << ' ' << f[n][1].S << '\n'; 
	if (f[2 * n][0].F <= n && f[2 * n][0].S >= n) last = 0;
	if (f[2 * n][1].F <= n && f[2 * n][1].S >= n) last = 1; 
	if (last < 0) {
		cout << -1;
		return 0; 
	}
	string res = "";
	int j = 2 * n; 
	int cur = n;
	while(j) {
		cur -= last; 
		int tmp;
		if (last) {
			res += 'B';
			tmp = b[j]; 
		}
		else {
			res += 'A';
			tmp = a[j]; 
		}
		if (a[j - 1] <= tmp && f[j - 1][0].F <= cur && f[j - 1][0].S >= cur) {
			last = 0;
		} 
		else {
			last = 1; 
		}
		j--; 
	}
	reverse(res.begin(), res.end()); 
	cout << res;
}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen("INP.INP" ,"r" , stdin) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
building4.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         freopen("OUT.OUT" , "w" , stdout) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 89 / 89