oj.uz

답안 #747203

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
747203 2023-05-23T22:56:38 Z finn__ 저장 (Saveit) (IOI10_saveit) C++17
0 / 100
 165 ms 6196 KB 
#include "grader.h"
#include "encoder.h"

#include <bits/stdc++.h>
using namespace std;

void encode_package(int p[3])
{
    int z = 0;
    for (size_t i = 0; i < 3; ++i)
        z = z * 3 + p[i] + 1;
    for (size_t i = 4; i < 5; --i)
        encode_bit((z >> i) & 1);
}

void encode(int n, int h, int m, int *a, int *b)
{
    if (!h)
        return;
    vector<vector<int>> g(n), d(h, vector<int>(n, -1));
    vector<int> p(n), bfs_order;
    for (size_t i = 0; i < m; ++i)
        g[a[i]].push_back(b[i]), g[b[i]].push_back(a[i]);
    for (size_t i = 0; i < n; ++i)
        sort(g[i].begin(), g[i].end());

    for (size_t i = 0; i < h; ++i)
    {
        queue<int> q;
        q.push(i);
        d[i][i] = 0;
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            for (int const &v : g[u])
                if (d[i][v] == -1)
                {
                    d[i][v] = d[i][u] + 1;
                    q.push(v);
                    if (!i)
                        p[v] = u, bfs_order.push_back(v);
                }
        }
    }

    assert(bfs_order.size() == n - 1);
    for (size_t i = 1; i < n; ++i) /* encode bfs tree from 0 */
        for (size_t j = 9; j < 10; --j)
            encode_bit((p[i] >> j) & 1);

    int c[3];
    size_t l = 0;
    for (int const &i : bfs_order) /* encode distance changes */
    {
        for (size_t k = 1; k < h; ++k)
        {
            c[l++] = d[k][i] - d[k][p[i]];
            if (l == 3)
                encode_package(c), l = 0;
        }
        printf("%d\n", i);
    }
    if (l)
        encode_package(c);
}

#include "grader.h"
#include "decoder.h"

#include <bits/stdc++.h>
using namespace std;

void decode_package(int p[3])
{
    int z = 0;
    for (size_t i = 0; i < 5; ++i)
        z = (z << 1) | decode_bit();
    for (size_t i = 2; i < 3; --i)
        p[i] = (z % 3) - 1, z /= 3;
}

void decode(int n, int h)
{
    if (!h)
        return;
    vector<vector<int>> t(n), d(h, vector<int>(n));
    vector<int> p(n), bfs_order;
    hops(0, 0, 0);
    for (size_t i = 1; i < n; ++i)
    {
        for (size_t j = 0; j < 10; ++j)
            p[i] = (p[i] << 1) | decode_bit();
        t[p[i]].push_back(i);
    }

    queue<int> q;
    q.push(0);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int const &v : t[u])
            bfs_order.push_back(v), q.push(v);
    }
    assert(bfs_order.size() == n - 1);
    for (int const &i : bfs_order)
        d[0][i] = d[0][p[i]] + 1, hops(0, i, d[0][i]);
    for (size_t i = 1; i < h; ++i)
        d[i][0] = d[0][i];

    size_t l = 3;
    int c[3];
    for (int const &i : bfs_order)
    {
        for (size_t k = 1; k < h; ++k)
        {
            if (l == 3)
                decode_package(c), l = 0;
            d[k][i] = d[k][p[i]] + c[l++];
            hops(k, i, d[k][i]);
        }
        printf("%d\n", i);
    }
}

Compilation message

encoder.cpp: In function 'void encode(int, int, int, int*, int*)':
encoder.cpp:22:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   22 |     for (size_t i = 0; i < m; ++i)
      |                        ~~^~~
encoder.cpp:24:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   24 |     for (size_t i = 0; i < n; ++i)
      |                        ~~^~~
encoder.cpp:27:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   27 |     for (size_t i = 0; i < h; ++i)
      |                        ~~^~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from encoder.cpp:4:
encoder.cpp:47:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |     assert(bfs_order.size() == n - 1);
      |            ~~~~~~~~~~~~~~~~~^~~~~~~~
encoder.cpp:48:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   48 |     for (size_t i = 1; i < n; ++i) /* encode bfs tree from 0 */
      |                        ~~^~~
encoder.cpp:56:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   56 |         for (size_t k = 1; k < h; ++k)
      |                            ~~^~~

decoder.cpp: In function 'void decode(int, int)':
decoder.cpp:23:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   23 |     for (size_t i = 1; i < n; ++i)
      |                        ~~^~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from decoder.cpp:4:
decoder.cpp:39:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 |     assert(bfs_order.size() == n - 1);
      |            ~~~~~~~~~~~~~~~~~^~~~~~~~
decoder.cpp:42:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   42 |     for (size_t i = 1; i < h; ++i)
      |                        ~~^~~
decoder.cpp:49:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   49 |         for (size_t k = 1; k < h; ++k)
      |                            ~~^~~

Subtask #1
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 165 ms 6196 KB Do not print anything to standard output: 1
2 Incorrect 0 ms 644 KB Do not print anything to standard output: 1
3 Incorrect 12 ms 1308 KB Do not print anything to standard output: 47
4 Incorrect 1 ms 648 KB Do not print anything to standard output: 1
5 Incorrect 14 ms 1404 KB Do not print anything to standard output: 28
6 Incorrect 13 ms 1396 KB Do not print anything to standard output: 40
7 Incorrect 32 ms 1592 KB Do not print anything to standard output: 10
8 Incorrect 10 ms 1156 KB Do not print anything to standard output: 108
9 Incorrect 10 ms 1284 KB Do not print anything to standard output: 559
10 Incorrect 11 ms 1316 KB Do not print anything to standard output: 7
11 Incorrect 17 ms 1424 KB Do not print anything to standard output: 364
12 Incorrect 11 ms 1252 KB Do not print anything to standard output: 103
13 Incorrect 32 ms 1820 KB Do not print anything to standard output: 1
14 Incorrect 11 ms 1300 KB Do not print anything to standard output: 468
15 Incorrect 11 ms 1364 KB Do not print anything to standard output: 12
16 Incorrect 41 ms 1712 KB Do not print anything to standard output: 12
17 Incorrect 24 ms 1660 KB Do not print anything to standard output: 11
18 Incorrect 47 ms 1880 KB Do not print anything to standard output: 1
19 Incorrect 27 ms 1552 KB Do not print anything to standard output: 16
20 Incorrect 46 ms 2240 KB Do not print anything to standard output: 52
21 Incorrect 54 ms 2272 KB Do not print anything to standard output: 3
22 Incorrect 39 ms 1868 KB Do not print anything to standard output: 22
23 Incorrect 53 ms 2588 KB Do not print anything to standard output: 83

Subtask #2
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 165 ms 6196 KB Do not print anything to standard output: 1
2 Incorrect 0 ms 644 KB Do not print anything to standard output: 1
3 Incorrect 12 ms 1308 KB Do not print anything to standard output: 47
4 Incorrect 1 ms 648 KB Do not print anything to standard output: 1
5 Incorrect 14 ms 1404 KB Do not print anything to standard output: 28
6 Incorrect 13 ms 1396 KB Do not print anything to standard output: 40
7 Incorrect 32 ms 1592 KB Do not print anything to standard output: 10
8 Incorrect 10 ms 1156 KB Do not print anything to standard output: 108
9 Incorrect 10 ms 1284 KB Do not print anything to standard output: 559
10 Incorrect 11 ms 1316 KB Do not print anything to standard output: 7
11 Incorrect 17 ms 1424 KB Do not print anything to standard output: 364
12 Incorrect 11 ms 1252 KB Do not print anything to standard output: 103
13 Incorrect 32 ms 1820 KB Do not print anything to standard output: 1
14 Incorrect 11 ms 1300 KB Do not print anything to standard output: 468
15 Incorrect 11 ms 1364 KB Do not print anything to standard output: 12
16 Incorrect 41 ms 1712 KB Do not print anything to standard output: 12
17 Incorrect 24 ms 1660 KB Do not print anything to standard output: 11
18 Incorrect 47 ms 1880 KB Do not print anything to standard output: 1
19 Incorrect 27 ms 1552 KB Do not print anything to standard output: 16
20 Incorrect 46 ms 2240 KB Do not print anything to standard output: 52
21 Incorrect 54 ms 2272 KB Do not print anything to standard output: 3
22 Incorrect 39 ms 1868 KB Do not print anything to standard output: 22
23 Incorrect 53 ms 2588 KB Do not print anything to standard output: 83

Subtask #3
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 165 ms 6196 KB Do not print anything to standard output: 1
2 Incorrect 0 ms 644 KB Do not print anything to standard output: 1
3 Incorrect 12 ms 1308 KB Do not print anything to standard output: 47
4 Incorrect 1 ms 648 KB Do not print anything to standard output: 1
5 Incorrect 14 ms 1404 KB Do not print anything to standard output: 28
6 Incorrect 13 ms 1396 KB Do not print anything to standard output: 40
7 Incorrect 32 ms 1592 KB Do not print anything to standard output: 10
8 Incorrect 10 ms 1156 KB Do not print anything to standard output: 108
9 Incorrect 10 ms 1284 KB Do not print anything to standard output: 559
10 Incorrect 11 ms 1316 KB Do not print anything to standard output: 7
11 Incorrect 17 ms 1424 KB Do not print anything to standard output: 364
12 Incorrect 11 ms 1252 KB Do not print anything to standard output: 103
13 Incorrect 32 ms 1820 KB Do not print anything to standard output: 1
14 Incorrect 11 ms 1300 KB Do not print anything to standard output: 468
15 Incorrect 11 ms 1364 KB Do not print anything to standard output: 12
16 Incorrect 41 ms 1712 KB Do not print anything to standard output: 12
17 Incorrect 24 ms 1660 KB Do not print anything to standard output: 11
18 Incorrect 47 ms 1880 KB Do not print anything to standard output: 1
19 Incorrect 27 ms 1552 KB Do not print anything to standard output: 16
20 Incorrect 46 ms 2240 KB Do not print anything to standard output: 52
21 Incorrect 54 ms 2272 KB Do not print anything to standard output: 3
22 Incorrect 39 ms 1868 KB Do not print anything to standard output: 22
23 Incorrect 53 ms 2588 KB Do not print anything to standard output: 83

Subtask #4
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 165 ms 6196 KB Do not print anything to standard output: 1
2 Incorrect 0 ms 644 KB Do not print anything to standard output: 1
3 Incorrect 12 ms 1308 KB Do not print anything to standard output: 47
4 Incorrect 1 ms 648 KB Do not print anything to standard output: 1
5 Incorrect 14 ms 1404 KB Do not print anything to standard output: 28
6 Incorrect 13 ms 1396 KB Do not print anything to standard output: 40
7 Incorrect 32 ms 1592 KB Do not print anything to standard output: 10
8 Incorrect 10 ms 1156 KB Do not print anything to standard output: 108
9 Incorrect 10 ms 1284 KB Do not print anything to standard output: 559
10 Incorrect 11 ms 1316 KB Do not print anything to standard output: 7
11 Incorrect 17 ms 1424 KB Do not print anything to standard output: 364
12 Incorrect 11 ms 1252 KB Do not print anything to standard output: 103
13 Incorrect 32 ms 1820 KB Do not print anything to standard output: 1
14 Incorrect 11 ms 1300 KB Do not print anything to standard output: 468
15 Incorrect 11 ms 1364 KB Do not print anything to standard output: 12
16 Incorrect 41 ms 1712 KB Do not print anything to standard output: 12
17 Incorrect 24 ms 1660 KB Do not print anything to standard output: 11
18 Incorrect 47 ms 1880 KB Do not print anything to standard output: 1
19 Incorrect 27 ms 1552 KB Do not print anything to standard output: 16
20 Incorrect 46 ms 2240 KB Do not print anything to standard output: 52
21 Incorrect 54 ms 2272 KB Do not print anything to standard output: 3
22 Incorrect 39 ms 1868 KB Do not print anything to standard output: 22
23 Incorrect 53 ms 2588 KB Do not print anything to standard output: 83