Submission #1285680

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285680		Jawad_Akbar_JJ	Building 4 (JOI20_building4)	C++20	100 / 100	627 ms	33692 KiB

building4

#include <iostream>

using namespace std;
const int N = 1<<20;
int a[N][2], Poss[N][2], n;
pair<int,int> Rng[N][2];
char Ans[N];

int main(){
    cin>>n;
    n += n;

    for (int i=1;i<=n;i++)
        cin>>a[i][0];
    for (int i=1;i<=n;i++)
        cin>>a[i][1];

    Poss[0][0] = 1;
    Rng[0][0] = {0, 0};

    for (int i=1;i<=n;i++){
        for (int k : {0, 1}){
            for (int j : {0, 1}){
                if (Poss[i-1][j] == 0 or a[i-1][j] > a[i][k])
                    continue;
                auto [l, r] = Rng[i][k];
                auto [L, R] = Rng[i-1][j];

                if (Poss[i][k] == 0)
                    Rng[i][k] = {L + !k, R + !k};
                else
                    Rng[i][k] = {min(L + !k, l), max(R + !k, r)};
                Poss[i][k] = 1;
            }
        }
    }

    int I = n, J = 0, countA = n / 2, cnt = 0, Ind = -1;
    if (!Poss[I][J] or Rng[I][J].first > countA or Rng[I][J].second < countA)
        J = 1;
    if (!Poss[I][J] or Rng[I][J].first > countA or Rng[I][J].second < countA)
        return cout<<"-1\n", 0;

    while (I != 0){
        Ans[I] = char('A' + J);
        countA -= !J;
        
        bool t = false;
        for (int k : {0, 1}){
            if (t == false and Poss[I-1][k] == 1 and a[I-1][k] <= a[I][J] and Rng[I-1][k].first <= countA and Rng[I-1][k].second >= countA){
                J = k;
                I = I - 1;
                t = true;
            }
        }
        if (t == false)
            cout<<1 / 0;
    }

    for (int i=1;i<=n;i++)
        cout<<Ans[i];
    cout<<'\n';
}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:57:21: warning: division by zero [-Wdiv-by-zero]
   57 |             cout<<1 / 0;
      |                   ~~^~~

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