제출 #1274289

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1274289		trinm01	건물 4 (JOI20_building4)	C++20	100 / 100	247 ms	126640 KiB

building4

// #pragma GCC optimize("O3")
// #pragma GCC optimization("Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;

#define int long long 
#define ll long long
#define FOR(i, l, r) for (int i = (l); i <= (r); i++)
#define FOD(i, r, l) for (int i = (r); i >= (l); i--)
#define fi first
#define se second
#define pii pair<int, int>

const ll mod = 1e9 + 7;
const int MAXN = 1e6 + 5;
const ll oo = 1e18 + 7;  
const int base = 10;

int n;
int a[MAXN][2];

pii f[MAXN][2];
pii merge(pii a, pii b){
	return {min(a.fi, b.fi), max(a.se, b.se)};
}
pii dp(int i, int t){
	if(i>n*2){
		return {0, 0};
	}
	if(f[i][t].fi!=-1){
		return f[i][t];
	}
	
	pii ans={oo, -oo};
	if(a[i][0]>=a[i-1][t]){
		pii p=dp(i+1, 0);
		ans=merge(ans, {p.fi+1, p.se+1});
	}
	if(a[i][1]>=a[i-1][t]){
		ans=merge(ans, dp(i+1, 1));
	}
	return f[i][t]=ans;
}

int sum=0;
void trace(int i, int t){
	if(i>n*2){
		return;
	}
	
	pii ans=f[i][t];
	if(a[i][0]>=a[i-1][t] && (n-(sum+1))>=dp(i+1, 0).fi && (n-(sum+1))<=dp(i+1, 0).se){
		cout << 'A';
		sum++;
		trace(i+1, 0);
	}
	else{
		cout << 'B';
		trace(i+1, 1);
	}
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    
    // freopen("test.txt", "r", stdin);
    // freopen("o2.out", "w", stdout);

    if(fopen(".inp", "r")){
        freopen(".inp", "r", stdin);
        freopen(".out", "w", stdout);
    }

    cin >> n;
    FOR(i, 1, n*2){
    	cin >> a[i][0];
    }
    FOR(i, 1, n*2){
    	cin >> a[i][1];
    }

	FOR(i, 0, n*2+1){
		FOR(t, 0, 1){
			f[i][t].fi=-1;
		}
	}
	
	pii p=dp(1, 0);
	// cout << p.fi << ' ' << p.se << '\n';
	if(p.fi>n || p.se<n){
		cout << -1;
		return 0;
	}
	// cout << 1;
	trace(1, 0);
	    
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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