oj.uz

Submission #240671

# Submission time Handle Problem Language Result Execution time Memory
240671 2020-06-20T14:49:18 Z robertnovistan Building 4 (JOI20_building4) C++14
11 / 100
 406 ms 49400 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 58 ms 45560 KB Output is correct
6 Correct 59 ms 44408 KB Output is correct
7 Correct 58 ms 39416 KB Output is correct
8 Correct 60 ms 42360 KB Output is correct
9 Correct 57 ms 43384 KB Output is correct
10 Correct 53 ms 38776 KB Output is correct
11 Correct 63 ms 46328 KB Output is correct
12 Correct 67 ms 49400 KB Output is correct
13 Correct 69 ms 49400 KB Output is correct
14 Correct 70 ms 49272 KB Output is correct
15 Correct 69 ms 49272 KB Output is correct
16 Correct 70 ms 49276 KB Output is correct
17 Correct 66 ms 49256 KB Output is correct
18 Correct 67 ms 49272 KB Output is correct
19 Correct 62 ms 49272 KB Output is correct
20 Correct 63 ms 49272 KB Output is correct
21 Correct 67 ms 49276 KB Output is correct
22 Correct 69 ms 49272 KB Output is correct
23 Correct 68 ms 49400 KB Output is correct
24 Correct 62 ms 49400 KB Output is correct
25 Correct 64 ms 49016 KB Output is correct
26 Correct 64 ms 49272 KB Output is correct
27 Correct 72 ms 49272 KB Output is correct
28 Correct 59 ms 44280 KB Output is correct
29 Correct 73 ms 49272 KB Output is correct
30 Correct 59 ms 44408 KB Output is correct
31 Correct 64 ms 49272 KB Output is correct
32 Correct 61 ms 41336 KB Output is correct
33 Correct 70 ms 49272 KB Output is correct

Subtask #2
0 / 89.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 58 ms 45560 KB Output is correct
6 Correct 59 ms 44408 KB Output is correct
7 Correct 58 ms 39416 KB Output is correct
8 Correct 60 ms 42360 KB Output is correct
9 Correct 57 ms 43384 KB Output is correct
10 Correct 53 ms 38776 KB Output is correct
11 Correct 63 ms 46328 KB Output is correct
12 Correct 67 ms 49400 KB Output is correct
13 Correct 69 ms 49400 KB Output is correct
14 Correct 70 ms 49272 KB Output is correct
15 Correct 69 ms 49272 KB Output is correct
16 Correct 70 ms 49276 KB Output is correct
17 Correct 66 ms 49256 KB Output is correct
18 Correct 67 ms 49272 KB Output is correct
19 Correct 62 ms 49272 KB Output is correct
20 Correct 63 ms 49272 KB Output is correct
21 Correct 67 ms 49276 KB Output is correct
22 Correct 69 ms 49272 KB Output is correct
23 Correct 68 ms 49400 KB Output is correct
24 Correct 62 ms 49400 KB Output is correct
25 Correct 64 ms 49016 KB Output is correct
26 Correct 64 ms 49272 KB Output is correct
27 Correct 72 ms 49272 KB Output is correct
28 Correct 59 ms 44280 KB Output is correct
29 Correct 73 ms 49272 KB Output is correct
30 Correct 59 ms 44408 KB Output is correct
31 Correct 64 ms 49272 KB Output is correct
32 Correct 61 ms 41336 KB Output is correct
33 Correct 70 ms 49272 KB Output is correct
34 Runtime error 406 ms 16120 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Halted 0 ms 0 KB -