Submission #810203

#	Time	Username	Problem	Language	Result	Execution time	Memory
810203		vjudge1	Building 4 (JOI20_building4)	C++17	100 / 100	261 ms	80868 KiB

building4

#include <bits/stdc++.h>



using namespace std;

#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define fi first
#define se second
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"


const int N = 1e6 + 9 , mod = 1e9 + 7;
ll  d[N] = {} , a[N] = {}, dp[N][2] = {},p[N][2][2] = {}, b[N] , c[N] , e[N] = {};

ll ans , ans1 = 0;
ll n1;
void max1(int x , int y , int l , int r , int k){
    ll i , j , m , n , s , f;
    if(dp[x][y] <= dp[l][r] + k)
        dp[x][y] = dp[l][r] + k , p[x][y][0] = l , p[x][y][1] = r;
    if(dp[x][y] == ans){
        while(x){
            if(c[x] != y)
                c[x] = 1 - c[x];
            ll x1 = x , y1 = y;
            x = p[x1][y1][0];
            y = p[x1][y1][1];
        }
        for(i = 1; i <= n1;i ++)
            if(ans1 != c[i])
            cout<<'B';
            else
                cout<<'A';
        exit(0);
    }
}



void solve(){
    ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
    cin>>n;
    n *= 2;
    for(i = 1; i <= n; i++)
        cin>>a[i];
    for(i = 1; i <= n; i++){
        cin>>b[i];
    }
    n1 = n;
    for(i = 1; i <= n; i++){
        if(max(a[i] , b[i]) < mx){
            cout<<-1<<"\n";
            return;
        }
        d[i] = mx;
        if(min(a[i] , b[i]) >= mx){
            if(b[i] == min(a[i] , b[i]))
                c[i] = 1;
        }else if(b[i] == max(a[i] , b[i]))
            c[i] = 1;
        s += c[i];
        if(c[i] == 1)
            mx = max(mx , b[i]);
        else
            mx= max(mx , a[i]);
    }
    if(s == n / 2){
        for(i = 1; i <= n; i++){
            if(c[i] == 1)
                cout<<'B';
            else
                cout<<'A';
        }
        return;
    }
    if(s > n / 2){
    ans1 = 1;
    s = mx = 0;
    swap(a , b);
    for(i = 1; i <= n; i++)
        c[i] = 1 - c[i] , s += c[i];
    }
    a[n + 1] = b[n + 1]= 1e18;
    for(i = 0; i <= n ; i++)
        dp[i][0] = dp[i][1] = -1e10;
    if(s < n / 2){
        s = n / 2 - s;
        ans = s;
        for(i = n; i >= 1; i--){
            //if(i == 7)
            //cout<<c[i]<<"\n";
            if(c[i] == 1){
                dp[i][1] = 0;
                if(i != n && a[i + 1] >= b[i])
                 max1(i , 1 , i + 1 , 0 , 0);
                if(i != n && b[i + 1] >= b[i])
                    max1(i , 1 , i + 1 , 1 , 0);
                if(a[i] >= d[i] && a[i] <= b[i + 1])
                    max1(i , 0 , i + 1 , 1 ,  -1);
                if(a[i] >= d[i] && a[i] <= a[i + 1])
                    max1(i, 0 , i + 1 , 0 ,  -1);
            }else{
                dp[i][0] = 0;
                if(i != n && a[i + 1] >= a[i])
                    max1(i, 0 , i + 1 , 0 , 0);
                if(i != n && b[i + 1] >= a[i])
                    max1(i , 0 , i + 1 , 1 , 0);

                if(b[i] >= d[i] && b[i] <= b[i + 1])
                    max1( i , 1 , i + 1 , 1 ,  1);
                if(b[i] >= d[i] && b[i] <= a[i + 1])
                    max1(i , 1  , i + 1 , 0 , 1);
            }
        }
    }
    cout<<-1<<"\n";
}

int main(){

     TL;
     /*
     #ifndef ONLINE_JUDGE
     freopen("input.txt", "r", stdin);
     freopen("output.txt", "w", stdout);
     #endif
     */
int t = 1;
//cin>>t;

while(t--)
     {
     solve();
     }

}
// Author : حسن

Compilation message (stderr)

building4.cpp: In function 'void max1(int, int, int, int, int)':
building4.cpp:31:12: warning: unused variable 'j' [-Wunused-variable]
   31 |     ll i , j , m , n , s , f;
      |            ^
building4.cpp:31:16: warning: unused variable 'm' [-Wunused-variable]
   31 |     ll i , j , m , n , s , f;
      |                ^
building4.cpp:31:20: warning: unused variable 'n' [-Wunused-variable]
   31 |     ll i , j , m , n , s , f;
      |                    ^
building4.cpp:31:24: warning: unused variable 's' [-Wunused-variable]
   31 |     ll i , j , m , n , s , f;
      |                        ^
building4.cpp:31:28: warning: unused variable 'f' [-Wunused-variable]
   31 |     ll i , j , m , n , s , f;
      |                            ^
building4.cpp: In function 'void solve()':
building4.cpp:54:8: warning: unused variable 'q' [-Wunused-variable]
   54 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |        ^
building4.cpp:54:16: warning: unused variable 'j' [-Wunused-variable]
   54 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                ^
building4.cpp:54:20: warning: unused variable 'm' [-Wunused-variable]
   54 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                    ^
building4.cpp:54:26: warning: unused variable 'z' [-Wunused-variable]
   54 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                          ^
building4.cpp:54:37: warning: unused variable 'f' [-Wunused-variable]
   54 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                     ^
building4.cpp:54:41: warning: unused variable 'l' [-Wunused-variable]
   54 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                         ^
building4.cpp:54:45: warning: unused variable 'r' [-Wunused-variable]
   54 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                             ^
building4.cpp:54:49: warning: unused variable 'k' [-Wunused-variable]
   54 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                                 ^
building4.cpp:54:53: warning: unused variable 'x' [-Wunused-variable]
   54 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                                     ^
building4.cpp:54:57: warning: unused variable 'y' [-Wunused-variable]
   54 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                                         ^
building4.cpp:54:61: warning: unused variable 'mn' [-Wunused-variable]
   54 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                                             ^~

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