oj.uz

Submission #894910

# Submission time Handle Problem Language Result Execution time Memory
894910 2023-12-29T07:58:28 Z sleepntsheep Saveit (IOI10_saveit) C++17
0 / 100
 166 ms 18384 KB 
#include "grader.h"
#include "encoder.h"
#include <vector>
#include <queue>


void send_int(int x, int nb)
{
    for (int j = 0; j < nb; ++j) encode_bit((x >> j) & 1);
}

#define N 1001

using namespace std;

vector<int> g[N];
int n, h;

vector<int> bfs(int u)
{
    vector<int> d(n, 1e9);
    queue<pair<int, int>> q;
    q.emplace(d[u] = 0, u);
    while (q.size())
    {
        auto [c, u] = q.front(); q.pop();
        for (auto v : g[u])
        {
            if (c + 1 < d[v])
                q.emplace(d[v] = c + 1, v);
        }
    }
    return d;
}

void encode(int n0, int h0, int ne, int *v1, int *v2){
    for (int i = 0; i < ne; ++i) g[v1[i]].push_back(v2[i]), g[v2[i]].push_back(v1[i]);
    ::n = n0; ::h = h0;

    for (int i = 0; i < h; ++i)
    {
        auto d = bfs(i);
        for (int j = 0; j < n; ++j)
        {
            if (d[j] <= 64)
            {
                send_int(1, 1);
                send_int(d[j], 6);
            }
            else
            {
                send_int(0, 1);
                send_int(d[j], 10);
            }
        }
    }

    return;
}


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

unsigned read_int(int nb)
{
    unsigned u = 0;
    for (int j = 0; j < nb; ++j) u |= decode_bit() << j;
    return u;
}

int n, h;

void decode(int v0, int h0) {
    ::n = v0; ::h = h0;
    for (int i = 0; i < h; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            int small = read_int(1);
            if (small)
                hops(i, j, read_int(6));
            else hops(i, j, read_int(10));
        }
    }
}

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 18384 KB Output is partially correct - 252000 call(s) of encode_bit()
2 Correct 2 ms 12036 KB Output is correct - 105 call(s) of encode_bit()
3 Correct 39 ms 12324 KB Output is partially correct - 226800 call(s) of encode_bit()
4 Correct 2 ms 12032 KB Output is correct - 175 call(s) of encode_bit()
5 Correct 37 ms 12684 KB Output is partially correct - 226800 call(s) of encode_bit()
6 Correct 44 ms 12624 KB Output is partially correct - 252000 call(s) of encode_bit()
7 Correct 50 ms 12972 KB Output is partially correct - 252000 call(s) of encode_bit()
8 Correct 37 ms 12208 KB Output is partially correct - 242172 call(s) of encode_bit()
9 Incorrect 50 ms 14444 KB Output isn't correct
10 Incorrect 50 ms 14276 KB Output isn't correct
11 Incorrect 43 ms 12560 KB Output isn't correct
12 Incorrect 55 ms 14360 KB Output isn't correct
13 Incorrect 63 ms 12908 KB Output isn't correct
14 Incorrect 51 ms 12456 KB Output isn't correct
15 Incorrect 60 ms 14540 KB Output isn't correct
16 Incorrect 60 ms 12640 KB Output isn't correct
17 Incorrect 60 ms 12824 KB Output isn't correct
18 Incorrect 55 ms 13072 KB Output isn't correct
19 Incorrect 56 ms 12832 KB Output isn't correct
20 Incorrect 65 ms 13296 KB Output isn't correct
21 Correct 69 ms 13440 KB Output is partially correct - 252000 call(s) of encode_bit()
22 Incorrect 61 ms 12768 KB Output isn't correct
23 Correct 78 ms 13400 KB Output is partially correct - 252000 call(s) of encode_bit()

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 18384 KB Output is partially correct - 252000 call(s) of encode_bit()
2 Correct 2 ms 12036 KB Output is correct - 105 call(s) of encode_bit()
3 Correct 39 ms 12324 KB Output is partially correct - 226800 call(s) of encode_bit()
4 Correct 2 ms 12032 KB Output is correct - 175 call(s) of encode_bit()
5 Correct 37 ms 12684 KB Output is partially correct - 226800 call(s) of encode_bit()
6 Correct 44 ms 12624 KB Output is partially correct - 252000 call(s) of encode_bit()
7 Correct 50 ms 12972 KB Output is partially correct - 252000 call(s) of encode_bit()
8 Correct 37 ms 12208 KB Output is partially correct - 242172 call(s) of encode_bit()
9 Incorrect 50 ms 14444 KB Output isn't correct
10 Incorrect 50 ms 14276 KB Output isn't correct
11 Incorrect 43 ms 12560 KB Output isn't correct
12 Incorrect 55 ms 14360 KB Output isn't correct
13 Incorrect 63 ms 12908 KB Output isn't correct
14 Incorrect 51 ms 12456 KB Output isn't correct
15 Incorrect 60 ms 14540 KB Output isn't correct
16 Incorrect 60 ms 12640 KB Output isn't correct
17 Incorrect 60 ms 12824 KB Output isn't correct
18 Incorrect 55 ms 13072 KB Output isn't correct
19 Incorrect 56 ms 12832 KB Output isn't correct
20 Incorrect 65 ms 13296 KB Output isn't correct
21 Correct 69 ms 13440 KB Output is partially correct - 252000 call(s) of encode_bit()
22 Incorrect 61 ms 12768 KB Output isn't correct
23 Correct 78 ms 13400 KB Output is partially correct - 252000 call(s) of encode_bit()

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 18384 KB Output is partially correct - 252000 call(s) of encode_bit()
2 Correct 2 ms 12036 KB Output is correct - 105 call(s) of encode_bit()
3 Correct 39 ms 12324 KB Output is partially correct - 226800 call(s) of encode_bit()
4 Correct 2 ms 12032 KB Output is correct - 175 call(s) of encode_bit()
5 Correct 37 ms 12684 KB Output is partially correct - 226800 call(s) of encode_bit()
6 Correct 44 ms 12624 KB Output is partially correct - 252000 call(s) of encode_bit()
7 Correct 50 ms 12972 KB Output is partially correct - 252000 call(s) of encode_bit()
8 Correct 37 ms 12208 KB Output is partially correct - 242172 call(s) of encode_bit()
9 Incorrect 50 ms 14444 KB Output isn't correct
10 Incorrect 50 ms 14276 KB Output isn't correct
11 Incorrect 43 ms 12560 KB Output isn't correct
12 Incorrect 55 ms 14360 KB Output isn't correct
13 Incorrect 63 ms 12908 KB Output isn't correct
14 Incorrect 51 ms 12456 KB Output isn't correct
15 Incorrect 60 ms 14540 KB Output isn't correct
16 Incorrect 60 ms 12640 KB Output isn't correct
17 Incorrect 60 ms 12824 KB Output isn't correct
18 Incorrect 55 ms 13072 KB Output isn't correct
19 Incorrect 56 ms 12832 KB Output isn't correct
20 Incorrect 65 ms 13296 KB Output isn't correct
21 Correct 69 ms 13440 KB Output is partially correct - 252000 call(s) of encode_bit()
22 Incorrect 61 ms 12768 KB Output isn't correct
23 Correct 78 ms 13400 KB Output is partially correct - 252000 call(s) of encode_bit()

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 18384 KB Output is partially correct - 252000 call(s) of encode_bit()
2 Correct 2 ms 12036 KB Output is correct - 105 call(s) of encode_bit()
3 Correct 39 ms 12324 KB Output is partially correct - 226800 call(s) of encode_bit()
4 Correct 2 ms 12032 KB Output is correct - 175 call(s) of encode_bit()
5 Correct 37 ms 12684 KB Output is partially correct - 226800 call(s) of encode_bit()
6 Correct 44 ms 12624 KB Output is partially correct - 252000 call(s) of encode_bit()
7 Correct 50 ms 12972 KB Output is partially correct - 252000 call(s) of encode_bit()
8 Correct 37 ms 12208 KB Output is partially correct - 242172 call(s) of encode_bit()
9 Incorrect 50 ms 14444 KB Output isn't correct
10 Incorrect 50 ms 14276 KB Output isn't correct
11 Incorrect 43 ms 12560 KB Output isn't correct
12 Incorrect 55 ms 14360 KB Output isn't correct
13 Incorrect 63 ms 12908 KB Output isn't correct
14 Incorrect 51 ms 12456 KB Output isn't correct
15 Incorrect 60 ms 14540 KB Output isn't correct
16 Incorrect 60 ms 12640 KB Output isn't correct
17 Incorrect 60 ms 12824 KB Output isn't correct
18 Incorrect 55 ms 13072 KB Output isn't correct
19 Incorrect 56 ms 12832 KB Output isn't correct
20 Incorrect 65 ms 13296 KB Output isn't correct
21 Correct 69 ms 13440 KB Output is partially correct - 252000 call(s) of encode_bit()
22 Incorrect 61 ms 12768 KB Output isn't correct
23 Correct 78 ms 13400 KB Output is partially correct - 252000 call(s) of encode_bit()