Submission #402145

#	Time	Username	Problem	Language	Result	Execution time	Memory
402145		cpp219	Building 4 (JOI20_building4)	C++14	100 / 100	374 ms	122552 KiB

building4

#pragma GCC optimization "O2"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")

#include <bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 1e6 + 6;
const ll Log2 = 19;
const ll inf = 1e9 + 7;
typedef pair<ll,ll> LL;
///Road to EF/M
LL dp[N][2];
ll n,a[N][2];

LL f(ll i,ll j){
    if (i == n) return {0,0};
    if (dp[i][j].fs != -1) return dp[i][j];
    LL ans = {inf,-inf};
    if (a[i][j] <= a[i + 1][0]){
        ans.fs = min(ans.fs,f(i + 1,0).fs);
        ans.sc = max(ans.sc,f(i + 1,0).sc);
    }
    if (a[i][j] <= a[i + 1][1]){
        ans.fs = min(ans.fs,f(i + 1,1).fs + 1);
        ans.sc = max(ans.sc,f(i + 1,1).sc + 1);
    }
    return dp[i][j] = ans;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define task "tst"
    if (fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        //freopen(task".out", "w", stdout);
    }
    cin>>n; n *= 2;
    for (ll i = 0;i <= n;i++) dp[i][0] = dp[i][1] = {-1,-1};
    for (ll i = 1;i <= n;i++) cin>>a[i][0];
    for (ll i = 1;i <= n;i++) cin>>a[i][1];
    //cout<<f(0,0).fs<<" "<<f(0,0).sc; return 0;
    if (f(0,0).fs > n/2 || f(0,0).sc < n/2) return cout<<-1,0;
    ll prv = 0,rm = n/2;
    for (ll i = 1;i <= n;i++){
        if (a[i][0] >= a[i - 1][prv]&&f(i,0).fs <= rm&&f(i,0).sc >= rm)
            prv = 0,cout<<"A";
        else{
            prv = 1; cout<<"B"; rm--;
        }
    }
}

Compilation message (stderr)

building4.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    1 | #pragma GCC optimization "O2"
      | 
building4.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization "unroll-loop"
      | 
building4.cpp: In function 'int main()':
building4.cpp:39:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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