Submission #240671

#	Time	Username	Problem	Language	Result	Execution time	Memory
240671		robertnovistan	Building 4 (JOI20_building4)	C++14	11 / 100	406 ms	49400 KiB

building4

#include <iostream>
#include <cstdio>
#include <bitset>
using namespace std;

const int MAX_BATIMENTS = (50 * 1000);

bitset <MAX_BATIMENTS> Accessibles[MAX_BATIMENTS][2];

int Luxures[MAX_BATIMENTS][2];

int nbBatiments;

void Read() {
    scanf("%d", &nbBatiments);
    nbBatiments *= 2;
    for (int i = 0; i < 2; i ++)
    {
        for (int j = 0; j < nbBatiments; j ++)
        {
            scanf("%d", &Luxures[j][i]);
        }
    }
    return;
}

void Treat(int ligne) {
    //int b = ligne % 2;
    //int a = (b + 1) % 2;
    int b = ligne;
    int a = ligne + 1;
    Accessibles[b][0] &= ~ Accessibles[b][0];
    Accessibles[b][1] &= ~ Accessibles[b][1];
    if (Luxures[ligne][1] <= Luxures[ligne + 1][0])
    {
        Accessibles[b][1] |= Accessibles[a][0];
    }
    if (Luxures[ligne][1] <= Luxures[ligne + 1][1])
    {
        Accessibles[b][1] |= Accessibles[a][1];
    }
    if (Luxures[ligne][0] <= Luxures[ligne + 1][0])
    {
        Accessibles[b][0] |= (Accessibles[a][0] << 1);
    }
    if (Luxures[ligne][0] <= Luxures[ligne + 1][1])
    {
        Accessibles[b][0] |= (Accessibles[a][1] << 1);
    }
    return;
}

void Backtrack(int ligne, int id, int valeur) {
    if (ligne >= nbBatiments - 1)
    {
        return;
    }
    if (id == 0)
    {
        valeur --;
    }
    if (valeur < 0)
    {
        printf("42");
        return;
    }
    if (Luxures[ligne][id] <= Luxures[ligne + 1][0] && Accessibles[ligne + 1][0][valeur])
    {
        printf("A");
        Backtrack(ligne + 1, 0, valeur);
    }
    else if (Luxures[ligne][id] <= Luxures[ligne + 1][1] && Accessibles[ligne + 1][1][valeur])
    {
        printf("B");
        Backtrack(ligne + 1, 1, valeur);
    }
    return;
}

void Solve() {
    //Accessibles[(nbBatiments - 1) % 2][0].set(1, 1);
    //Accessibles[(nbBatiments - 1) % 2][1].set(0, 1);
    Accessibles[nbBatiments - 1][0].set(1, 1);
    Accessibles[nbBatiments - 1][1].set(0, 1);
    for (int i = nbBatiments - 2; i >= 0; i --)
    {
        Treat(i);
    }
    if (!Accessibles[0][0][nbBatiments / 2] && !Accessibles[0][1][nbBatiments / 2])
    {
        printf("-1\n");
    }
    if (Accessibles[0][0][nbBatiments / 2])
    {
        printf("A");
        Backtrack(0, 0, nbBatiments / 2);
    }
    else if (Accessibles[0][1][nbBatiments / 2])
    {
        printf("B");
        Backtrack(0, 1, nbBatiments / 2);
    }
    printf("\n");
    return;
    for (int i = 0; i <= nbBatiments; i ++)
    {
        if (Accessibles[0][0][i])
        {
            printf("1");
        }
        else
        {
            printf("0");
        }
    }
    
    printf("\n");
    return;
}

int main() {
    Read();
    Solve();
    return 0;
}

Compilation message (stderr)

building4.cpp: In function 'void Read()':
building4.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &nbBatiments);
     ~~~~~^~~~~~~~~~~~~~~~~~~~
building4.cpp:21:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &Luxures[j][i]);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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