oj.uz

Submission #435579

# Submission time Handle Problem Language Result Execution time Memory
435579 2021-06-23T12:46:48 Z Ozy Fountain Parks (IOI21_parks) C++17
100 / 100
 930 ms 55512 KB 
#include "parks.h"
#include <bits/stdc++.h>

using namespace std;

#define lli long long
#define rep(i, a, b) for(lli i = (a); i <= (b); ++i)
#define repa(i, a, b) for(lli i = (a); i >= (b); --i)

#define nl "\n"
#define debugsl(x) cout << #x << " = " << x << ", "
#define debug(x) debugsl(x) << nl
#define debugarr(x, a, b) cout << #x << " = ["; rep(ii, a, b) cout << x[ii] << ", "; cout << "]" << nl

#define MAX_N 200002

int dx[6] = {0, -2, 0, 2, 2, -2}; // 0-NORTE, 1-OESTE, 2-SUR, 3-ESTE, 4-NORESTE, 5-SUROESTE
int dy[6] = {2, 0, -2, 0, 2, -2};
#define norte 0
#define oeste 1
#define sur 2
#define este 3
#define noreste 4
#define suroeste 5

map<pair<int, int>, int> fuentes;
int visitada[MAX_N];
int grupo[MAX_N], gfinal;
std::vector<int> u, v, a, b;

int comp(int a){
    if (grupo[a] == a) return a;
    else return grupo[a] = comp(grupo[a]);
}

bool une(int a, int b){
    int ga = comp(a);
    int gb = comp(b);
    if (ga == gb) return false;
    grupo[ga] = gb;
    return true;
}

void dfs(int nodo, int padre, vector<int> &x, vector<int> &y){

    bool hayfuente[6], diagimpar, camino[6];
    int fuente[6];

    visitada[nodo] = 1;

    // VALIDA EN QUE DIRECCIONES TIENE FUENTE
    rep(i, norte, suroeste) camino[i] = false, hayfuente[i] = fuentes.find({x[nodo] + dx[i], y[nodo] + dy[i]}) != fuentes.end();

    // OBTEN LA FUENTE EN CADA DIRECCION
    rep(i, norte, suroeste)
        if (hayfuente[i]) fuente[i] = fuentes[{x[nodo] + dx[i], y[nodo] + dy[i]}];
        else fuente[i] = -1;

    // VALIDA EN QUE DIAGONAL ESTAS
    diagimpar = (x[nodo] + y[nodo]) & 3;

    // LOS CASOS QUE HAY QUE REVISAR ES CUANDO LA FUENTE QUE ESTAMOS PROCESANDO PERTENECE A UN CUADRADO DE 2x2,
    // EN ESOS CASOS SE DEBE EVITAR COLOCAR LOS CAMINOS QUE COLISIONAN.
    // EN PARTICULAR SE EVITARA COLOCAR LOS CAMINOS NORTE O ESTE QUE COLISIONARIAN CON UN CAMINO SUR U OESTE DE UN MISMO CUADRADO

    if (hayfuente[norte] && hayfuente[este] && hayfuente[noreste]){ // EL NODO ES LA ESQUINA SUROESTE DE UN CUADRADO DE 2x2
        // DEPENDIENDO DE LA DIAGONAL COLOCA UNICAMENTE EL CAMINO NORTE O EL ESTE
        if (diagimpar){ // UNE SOLO AL NORTE
            if (une(nodo, fuente[norte])){
                u.push_back(nodo);
                v.push_back(fuente[norte]);
                a.push_back(x[nodo] - 1); // BANCA AL OESTE
                b.push_back((y[nodo] + y[fuente[norte]]) / 2);
                camino[norte] = true;
            }
        }
        else{ // UNE SOLO AL ESTE
            if (une(nodo, fuente[este])){
                u.push_back(nodo);
                v.push_back(fuente[este]);
                a.push_back((x[nodo] + x[fuente[este]]) / 2);
                b.push_back(y[nodo] - 1); // BANCA AL SUR
                camino[este] = true;
            }
        }
    }
    else{
        // SI NO ES UN CUADRO UNE LIBREMENTE AL NORTE Y AL ESTE
        if (hayfuente[norte] && une(nodo, fuente[norte])){
            u.push_back(nodo);
            v.push_back(fuente[norte]);
            b.push_back((y[nodo] + y[fuente[norte]]) / 2);
            if (diagimpar) a.push_back(x[nodo] - 1);
            else a.push_back(x[nodo] + 1);
            camino[norte] = true;
        }
        if (hayfuente[este] && une(nodo, fuente[este])){
            u.push_back(nodo);
            v.push_back(fuente[este]);
            a.push_back((x[nodo] + x[fuente[este]]) / 2);
            if (diagimpar) b.push_back(y[nodo] + 1);
            else b.push_back(y[nodo] - 1);
            camino[este] = true;
        }
    }

    // DESPUES DE UNIR, CONTINUA LA DFS A LAS FUENTES A LAS QUE CONSTRUISTE CAMINO
    rep(i, norte, este) if (hayfuente[i] && camino[i]) dfs(fuente[i], nodo, x, y);
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
    if (x.size() == 1) {
	build({}, {}, {}, {});
        return 1;
    }

    // AGREGA LAS FUENTES A UN MAP PARA PODER BUSCARLAS FACILMENTE
    rep(i, 0, x.size() - 1) fuentes[{x[i], y[i]}] = i;

    // AHORA HAZ UNA BUSQUEDA EN PROFUNDIDAD DESDE CUALQUIER FUENTE,
    // SE VAN A AGREGAR CAMINOS UNICAMENTE SI SON NECESARIOS PARA QUE EL GRAFO SEA CONEXO (SE VALIDA MEDIANTE UN DSU)
    // PARA ACOMODAR LAS BANCAS DE FORMA QUE NO CHOQUEN SE UTILIZAN LAS DIAGONALES, EN ESTE CASO SE USAN LAS DE TIPO (x + y),
    // LA IDEA ES QUE TODOS LOS CAMINOS VERTICALES QUE QUEDEN ENTRE UN PAR DE DIAGONALES TENGAN LA BANCA DEL MISMO LADO, LO MISMO CON LOS HORIZONTALES.
    // ADEMAS, LOS CAMINOS ENTRE UN PAR DE DIAGONALES Y EL PAR DE DIAGONALES INMEDIATAMENTE SIGUIENTE ALTERNAN SU LADO.
    //     H
    //   \---\---\   \   \      LAS LETRAS H CORRESPONDEN A LA BANCA DEL CAMINO HORIZONTAL
    //    \  |\h |\   \   \     LAS LETRAS V CORRESPONDEN A LA BANCA DEL CAMINO VERTICAL
    //     \V| \ |V\   \   \    LAS LETRAS h EN EL DIBUJO SON BANCAS QUE COLISIONAN
    //      \| h\|  \   \   \
    //       \---\---\   \   \
    //             H
    // LAS BANCAS ENTRE UN PAR DE DIAGONALES NUNCA VAN A COLISIONAR.
    // LA UNICA FORMA DE COLISIONAR ES DOS CAMINOS HORIZONTALES O VERTICALES ENCONTRADOS EN PARES DE DIAGONALES CONSECUTIVOS.
    // PARA QUE ESTO SEA POSIBLE ES FORZOSO QUE HAYA UN CUADRO DE 2x2 CON FUENTES EN LAS 4 ESQUINAS

    rep(i, 0, x.size() - 1) grupo[i] = i; // INICIALIZA EL DSU

    // VISITA TODAS LAS FUENTES UNIENDO SOLO HACIA EL NORTE Y AL ESTE
    rep(i, 0, x.size() - 1) if (!visitada[i]) dfs(i, -1, x, y);

    // VERIFICA SI TODOS QUEDARON UNIDOS EN EL MISMO COMPONENTE
    bool ok = true;
    gfinal = comp(0);
    rep(i, 1, x.size() - 1) if (comp(i) != gfinal){
        ok = false;
        break;
    }

    if (!ok) return 0;

    build(u, v, a, b);
    return 1;
}

Compilation message

parks.cpp:129:5: warning: multi-line comment [-Wcomment]
  129 |     //      \| h\|  \   \   \
      |     ^
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:7:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define rep(i, a, b) for(lli i = (a); i <= (b); ++i)
      |                                         ^
parks.cpp:118:5: note: in expansion of macro 'rep'
  118 |     rep(i, 0, x.size() - 1) fuentes[{x[i], y[i]}] = i;
      |     ^~~
parks.cpp:7:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define rep(i, a, b) for(lli i = (a); i <= (b); ++i)
      |                                         ^
parks.cpp:136:5: note: in expansion of macro 'rep'
  136 |     rep(i, 0, x.size() - 1) grupo[i] = i; // INICIALIZA EL DSU
      |     ^~~
parks.cpp:7:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define rep(i, a, b) for(lli i = (a); i <= (b); ++i)
      |                                         ^
parks.cpp:139:5: note: in expansion of macro 'rep'
  139 |     rep(i, 0, x.size() - 1) if (!visitada[i]) dfs(i, -1, x, y);
      |     ^~~
parks.cpp:7:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define rep(i, a, b) for(lli i = (a); i <= (b); ++i)
      |                                         ^
parks.cpp:144:5: note: in expansion of macro 'rep'
  144 |     rep(i, 1, x.size() - 1) if (comp(i) != gfinal){
      |     ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 245 ms 29608 KB Output is correct
10 Correct 16 ms 3556 KB Output is correct
11 Correct 98 ms 16828 KB Output is correct
12 Correct 28 ms 5080 KB Output is correct
13 Correct 62 ms 10096 KB Output is correct
14 Correct 2 ms 460 KB Output is correct
15 Correct 2 ms 588 KB Output is correct
16 Correct 173 ms 21988 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 245 ms 29608 KB Output is correct
10 Correct 16 ms 3556 KB Output is correct
11 Correct 98 ms 16828 KB Output is correct
12 Correct 28 ms 5080 KB Output is correct
13 Correct 62 ms 10096 KB Output is correct
14 Correct 2 ms 460 KB Output is correct
15 Correct 2 ms 588 KB Output is correct
16 Correct 173 ms 21988 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 690 ms 32892 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Correct 3 ms 460 KB Output is correct
26 Correct 5 ms 704 KB Output is correct
27 Correct 7 ms 776 KB Output is correct
28 Correct 274 ms 14792 KB Output is correct
29 Correct 404 ms 24268 KB Output is correct
30 Correct 602 ms 34380 KB Output is correct
31 Correct 800 ms 38920 KB Output is correct
32 Correct 1 ms 204 KB Output is correct
33 Correct 1 ms 204 KB Output is correct
34 Correct 1 ms 204 KB Output is correct
35 Correct 1 ms 204 KB Output is correct
36 Correct 1 ms 204 KB Output is correct
37 Correct 1 ms 204 KB Output is correct
38 Correct 1 ms 204 KB Output is correct
39 Correct 1 ms 204 KB Output is correct
40 Correct 1 ms 204 KB Output is correct
41 Correct 1 ms 204 KB Output is correct
42 Correct 0 ms 204 KB Output is correct
43 Correct 3 ms 460 KB Output is correct
44 Correct 5 ms 588 KB Output is correct
45 Correct 276 ms 13688 KB Output is correct
46 Correct 442 ms 20012 KB Output is correct
47 Correct 433 ms 20004 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 245 ms 29608 KB Output is correct
10 Correct 16 ms 3556 KB Output is correct
11 Correct 98 ms 16828 KB Output is correct
12 Correct 28 ms 5080 KB Output is correct
13 Correct 62 ms 10096 KB Output is correct
14 Correct 2 ms 460 KB Output is correct
15 Correct 2 ms 588 KB Output is correct
16 Correct 173 ms 21988 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 690 ms 32892 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Correct 3 ms 460 KB Output is correct
26 Correct 5 ms 704 KB Output is correct
27 Correct 7 ms 776 KB Output is correct
28 Correct 274 ms 14792 KB Output is correct
29 Correct 404 ms 24268 KB Output is correct
30 Correct 602 ms 34380 KB Output is correct
31 Correct 800 ms 38920 KB Output is correct
32 Correct 1 ms 204 KB Output is correct
33 Correct 1 ms 204 KB Output is correct
34 Correct 1 ms 204 KB Output is correct
35 Correct 1 ms 204 KB Output is correct
36 Correct 1 ms 204 KB Output is correct
37 Correct 1 ms 204 KB Output is correct
38 Correct 1 ms 204 KB Output is correct
39 Correct 1 ms 204 KB Output is correct
40 Correct 1 ms 204 KB Output is correct
41 Correct 1 ms 204 KB Output is correct
42 Correct 0 ms 204 KB Output is correct
43 Correct 3 ms 460 KB Output is correct
44 Correct 5 ms 588 KB Output is correct
45 Correct 276 ms 13688 KB Output is correct
46 Correct 442 ms 20012 KB Output is correct
47 Correct 433 ms 20004 KB Output is correct
48 Correct 1 ms 204 KB Output is correct
49 Correct 1 ms 204 KB Output is correct
50 Correct 1 ms 204 KB Output is correct
51 Correct 1 ms 204 KB Output is correct
52 Correct 1 ms 204 KB Output is correct
53 Correct 1 ms 204 KB Output is correct
54 Correct 1 ms 204 KB Output is correct
55 Correct 838 ms 30360 KB Output is correct
56 Correct 1 ms 204 KB Output is correct
57 Correct 4 ms 588 KB Output is correct
58 Correct 15 ms 1312 KB Output is correct
59 Correct 22 ms 1484 KB Output is correct
60 Correct 313 ms 19180 KB Output is correct
61 Correct 488 ms 21852 KB Output is correct
62 Correct 653 ms 25452 KB Output is correct
63 Correct 930 ms 34784 KB Output is correct
64 Correct 1 ms 204 KB Output is correct
65 Correct 1 ms 204 KB Output is correct
66 Correct 1 ms 204 KB Output is correct
67 Correct 433 ms 39080 KB Output is correct
68 Correct 466 ms 36516 KB Output is correct
69 Correct 424 ms 38116 KB Output is correct
70 Correct 7 ms 716 KB Output is correct
71 Correct 13 ms 1148 KB Output is correct
72 Correct 287 ms 13700 KB Output is correct
73 Correct 509 ms 20500 KB Output is correct
74 Correct 762 ms 27032 KB Output is correct
75 Correct 480 ms 40876 KB Output is correct
76 Correct 432 ms 37928 KB Output is correct
77 Correct 8 ms 844 KB Output is correct
78 Correct 14 ms 1356 KB Output is correct
79 Correct 264 ms 13756 KB Output is correct
80 Correct 478 ms 20428 KB Output is correct
81 Correct 695 ms 27420 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 245 ms 29608 KB Output is correct
10 Correct 16 ms 3556 KB Output is correct
11 Correct 98 ms 16828 KB Output is correct
12 Correct 28 ms 5080 KB Output is correct
13 Correct 62 ms 10096 KB Output is correct
14 Correct 2 ms 460 KB Output is correct
15 Correct 2 ms 588 KB Output is correct
16 Correct 173 ms 21988 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 839 ms 27480 KB Output is correct
21 Correct 516 ms 37428 KB Output is correct
22 Correct 872 ms 27292 KB Output is correct
23 Correct 399 ms 33952 KB Output is correct
24 Correct 544 ms 17488 KB Output is correct
25 Correct 604 ms 21028 KB Output is correct
26 Correct 358 ms 20756 KB Output is correct
27 Correct 414 ms 27288 KB Output is correct
28 Correct 434 ms 27108 KB Output is correct
29 Correct 589 ms 27188 KB Output is correct
30 Correct 710 ms 27304 KB Output is correct
31 Correct 1 ms 204 KB Output is correct
32 Correct 36 ms 2460 KB Output is correct
33 Correct 193 ms 8876 KB Output is correct
34 Correct 487 ms 55512 KB Output is correct
35 Correct 20 ms 1356 KB Output is correct
36 Correct 129 ms 5600 KB Output is correct
37 Correct 315 ms 10628 KB Output is correct
38 Correct 258 ms 11200 KB Output is correct
39 Correct 401 ms 15396 KB Output is correct
40 Correct 535 ms 19684 KB Output is correct
41 Correct 714 ms 23424 KB Output is correct
42 Correct 845 ms 27960 KB Output is correct
43 Correct 1 ms 204 KB Output is correct
44 Correct 1 ms 204 KB Output is correct
45 Correct 1 ms 204 KB Output is correct
46 Correct 1 ms 204 KB Output is correct
47 Correct 1 ms 204 KB Output is correct
48 Correct 1 ms 204 KB Output is correct
49 Correct 1 ms 204 KB Output is correct
50 Correct 1 ms 204 KB Output is correct
51 Correct 1 ms 204 KB Output is correct
52 Correct 1 ms 204 KB Output is correct
53 Correct 1 ms 204 KB Output is correct
54 Correct 4 ms 460 KB Output is correct
55 Correct 5 ms 588 KB Output is correct
56 Correct 270 ms 13752 KB Output is correct
57 Correct 459 ms 20000 KB Output is correct
58 Correct 444 ms 19996 KB Output is correct
59 Correct 1 ms 204 KB Output is correct
60 Correct 1 ms 204 KB Output is correct
61 Correct 1 ms 204 KB Output is correct
62 Correct 457 ms 39168 KB Output is correct
63 Correct 439 ms 36400 KB Output is correct
64 Correct 479 ms 38096 KB Output is correct
65 Correct 7 ms 716 KB Output is correct
66 Correct 14 ms 1156 KB Output is correct
67 Correct 305 ms 13620 KB Output is correct
68 Correct 566 ms 20380 KB Output is correct
69 Correct 785 ms 27024 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 245 ms 29608 KB Output is correct
10 Correct 16 ms 3556 KB Output is correct
11 Correct 98 ms 16828 KB Output is correct
12 Correct 28 ms 5080 KB Output is correct
13 Correct 62 ms 10096 KB Output is correct
14 Correct 2 ms 460 KB Output is correct
15 Correct 2 ms 588 KB Output is correct
16 Correct 173 ms 21988 KB Output is correct
17 Correct 527 ms 37252 KB Output is correct
18 Correct 479 ms 39828 KB Output is correct
19 Correct 734 ms 32608 KB Output is correct
20 Correct 606 ms 26588 KB Output is correct
21 Correct 515 ms 23936 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 77 ms 5192 KB Output is correct
24 Correct 34 ms 2500 KB Output is correct
25 Correct 151 ms 7748 KB Output is correct
26 Correct 286 ms 12636 KB Output is correct
27 Correct 265 ms 14216 KB Output is correct
28 Correct 362 ms 17612 KB Output is correct
29 Correct 460 ms 21012 KB Output is correct
30 Correct 551 ms 24080 KB Output is correct
31 Correct 632 ms 27772 KB Output is correct
32 Correct 513 ms 40784 KB Output is correct
33 Correct 437 ms 38028 KB Output is correct
34 Correct 8 ms 844 KB Output is correct
35 Correct 14 ms 1392 KB Output is correct
36 Correct 257 ms 13768 KB Output is correct
37 Correct 446 ms 20652 KB Output is correct
38 Correct 652 ms 27232 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 245 ms 29608 KB Output is correct
10 Correct 16 ms 3556 KB Output is correct
11 Correct 98 ms 16828 KB Output is correct
12 Correct 28 ms 5080 KB Output is correct
13 Correct 62 ms 10096 KB Output is correct
14 Correct 2 ms 460 KB Output is correct
15 Correct 2 ms 588 KB Output is correct
16 Correct 173 ms 21988 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 690 ms 32892 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Correct 3 ms 460 KB Output is correct
26 Correct 5 ms 704 KB Output is correct
27 Correct 7 ms 776 KB Output is correct
28 Correct 274 ms 14792 KB Output is correct
29 Correct 404 ms 24268 KB Output is correct
30 Correct 602 ms 34380 KB Output is correct
31 Correct 800 ms 38920 KB Output is correct
32 Correct 1 ms 204 KB Output is correct
33 Correct 1 ms 204 KB Output is correct
34 Correct 1 ms 204 KB Output is correct
35 Correct 1 ms 204 KB Output is correct
36 Correct 1 ms 204 KB Output is correct
37 Correct 1 ms 204 KB Output is correct
38 Correct 1 ms 204 KB Output is correct
39 Correct 1 ms 204 KB Output is correct
40 Correct 1 ms 204 KB Output is correct
41 Correct 1 ms 204 KB Output is correct
42 Correct 0 ms 204 KB Output is correct
43 Correct 3 ms 460 KB Output is correct
44 Correct 5 ms 588 KB Output is correct
45 Correct 276 ms 13688 KB Output is correct
46 Correct 442 ms 20012 KB Output is correct
47 Correct 433 ms 20004 KB Output is correct
48 Correct 1 ms 204 KB Output is correct
49 Correct 1 ms 204 KB Output is correct
50 Correct 1 ms 204 KB Output is correct
51 Correct 1 ms 204 KB Output is correct
52 Correct 1 ms 204 KB Output is correct
53 Correct 1 ms 204 KB Output is correct
54 Correct 1 ms 204 KB Output is correct
55 Correct 838 ms 30360 KB Output is correct
56 Correct 1 ms 204 KB Output is correct
57 Correct 4 ms 588 KB Output is correct
58 Correct 15 ms 1312 KB Output is correct
59 Correct 22 ms 1484 KB Output is correct
60 Correct 313 ms 19180 KB Output is correct
61 Correct 488 ms 21852 KB Output is correct
62 Correct 653 ms 25452 KB Output is correct
63 Correct 930 ms 34784 KB Output is correct
64 Correct 1 ms 204 KB Output is correct
65 Correct 1 ms 204 KB Output is correct
66 Correct 1 ms 204 KB Output is correct
67 Correct 433 ms 39080 KB Output is correct
68 Correct 466 ms 36516 KB Output is correct
69 Correct 424 ms 38116 KB Output is correct
70 Correct 7 ms 716 KB Output is correct
71 Correct 13 ms 1148 KB Output is correct
72 Correct 287 ms 13700 KB Output is correct
73 Correct 509 ms 20500 KB Output is correct
74 Correct 762 ms 27032 KB Output is correct
75 Correct 480 ms 40876 KB Output is correct
76 Correct 432 ms 37928 KB Output is correct
77 Correct 8 ms 844 KB Output is correct
78 Correct 14 ms 1356 KB Output is correct
79 Correct 264 ms 13756 KB Output is correct
80 Correct 478 ms 20428 KB Output is correct
81 Correct 695 ms 27420 KB Output is correct
82 Correct 1 ms 204 KB Output is correct
83 Correct 1 ms 204 KB Output is correct
84 Correct 1 ms 204 KB Output is correct
85 Correct 839 ms 27480 KB Output is correct
86 Correct 516 ms 37428 KB Output is correct
87 Correct 872 ms 27292 KB Output is correct
88 Correct 399 ms 33952 KB Output is correct
89 Correct 544 ms 17488 KB Output is correct
90 Correct 604 ms 21028 KB Output is correct
91 Correct 358 ms 20756 KB Output is correct
92 Correct 414 ms 27288 KB Output is correct
93 Correct 434 ms 27108 KB Output is correct
94 Correct 589 ms 27188 KB Output is correct
95 Correct 710 ms 27304 KB Output is correct
96 Correct 1 ms 204 KB Output is correct
97 Correct 36 ms 2460 KB Output is correct
98 Correct 193 ms 8876 KB Output is correct
99 Correct 487 ms 55512 KB Output is correct
100 Correct 20 ms 1356 KB Output is correct
101 Correct 129 ms 5600 KB Output is correct
102 Correct 315 ms 10628 KB Output is correct
103 Correct 258 ms 11200 KB Output is correct
104 Correct 401 ms 15396 KB Output is correct
105 Correct 535 ms 19684 KB Output is correct
106 Correct 714 ms 23424 KB Output is correct
107 Correct 845 ms 27960 KB Output is correct
108 Correct 1 ms 204 KB Output is correct
109 Correct 1 ms 204 KB Output is correct
110 Correct 1 ms 204 KB Output is correct
111 Correct 1 ms 204 KB Output is correct
112 Correct 1 ms 204 KB Output is correct
113 Correct 1 ms 204 KB Output is correct
114 Correct 1 ms 204 KB Output is correct
115 Correct 1 ms 204 KB Output is correct
116 Correct 1 ms 204 KB Output is correct
117 Correct 1 ms 204 KB Output is correct
118 Correct 1 ms 204 KB Output is correct
119 Correct 4 ms 460 KB Output is correct
120 Correct 5 ms 588 KB Output is correct
121 Correct 270 ms 13752 KB Output is correct
122 Correct 459 ms 20000 KB Output is correct
123 Correct 444 ms 19996 KB Output is correct
124 Correct 1 ms 204 KB Output is correct
125 Correct 1 ms 204 KB Output is correct
126 Correct 1 ms 204 KB Output is correct
127 Correct 457 ms 39168 KB Output is correct
128 Correct 439 ms 36400 KB Output is correct
129 Correct 479 ms 38096 KB Output is correct
130 Correct 7 ms 716 KB Output is correct
131 Correct 14 ms 1156 KB Output is correct
132 Correct 305 ms 13620 KB Output is correct
133 Correct 566 ms 20380 KB Output is correct
134 Correct 785 ms 27024 KB Output is correct
135 Correct 527 ms 37252 KB Output is correct
136 Correct 479 ms 39828 KB Output is correct
137 Correct 734 ms 32608 KB Output is correct
138 Correct 606 ms 26588 KB Output is correct
139 Correct 515 ms 23936 KB Output is correct
140 Correct 1 ms 204 KB Output is correct
141 Correct 77 ms 5192 KB Output is correct
142 Correct 34 ms 2500 KB Output is correct
143 Correct 151 ms 7748 KB Output is correct
144 Correct 286 ms 12636 KB Output is correct
145 Correct 265 ms 14216 KB Output is correct
146 Correct 362 ms 17612 KB Output is correct
147 Correct 460 ms 21012 KB Output is correct
148 Correct 551 ms 24080 KB Output is correct
149 Correct 632 ms 27772 KB Output is correct
150 Correct 513 ms 40784 KB Output is correct
151 Correct 437 ms 38028 KB Output is correct
152 Correct 8 ms 844 KB Output is correct
153 Correct 14 ms 1392 KB Output is correct
154 Correct 257 ms 13768 KB Output is correct
155 Correct 446 ms 20652 KB Output is correct
156 Correct 652 ms 27232 KB Output is correct
157 Correct 1 ms 204 KB Output is correct
158 Correct 1 ms 204 KB Output is correct
159 Correct 1 ms 204 KB Output is correct
160 Correct 1 ms 204 KB Output is correct
161 Correct 676 ms 27168 KB Output is correct
162 Correct 475 ms 49028 KB Output is correct
163 Correct 728 ms 41796 KB Output is correct
164 Correct 716 ms 40604 KB Output is correct
165 Correct 648 ms 34768 KB Output is correct
166 Correct 648 ms 29100 KB Output is correct
167 Correct 138 ms 6628 KB Output is correct
168 Correct 57 ms 3644 KB Output is correct
169 Correct 192 ms 8572 KB Output is correct
170 Correct 409 ms 15928 KB Output is correct
171 Correct 637 ms 20800 KB Output is correct
172 Correct 279 ms 14076 KB Output is correct
173 Correct 359 ms 16664 KB Output is correct
174 Correct 429 ms 19392 KB Output is correct
175 Correct 504 ms 21972 KB Output is correct
176 Correct 620 ms 24988 KB Output is correct
177 Correct 667 ms 27808 KB Output is correct