oj.uz

Submission #371247

# Submission time Handle Problem Language Result Execution time Memory
371247 2021-02-26T09:38:25 Z Sorting Saveit (IOI10_saveit) C++17
100 / 100
 280 ms 11228 KB 
#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 1000 + 3;
const int H = 36 + 3;
const int INF = 1e9;

static vector<int> adj[N];
static int n, h, m, par[N], d[N];
static bool vis[N];
static vector<int> en_diff;

void encode_num(int x){
    for(int i = 9; i >= 0; --i)
        encode_bit((x >> i) & 1);
}

void encode_diff(int diff){
    en_diff.push_back(diff);
}

void add_simple(int diff){
    ++diff;
    for(int i = 1; i >= 0; --i)
        encode_bit((diff >> i) & 1);
}

void bfs_0(int u, int p = -1){
    queue<int> q;
    q.push(u);
    vis[u] = true;

    while(!q.empty()){
        int v = q.front();
        q.pop();

        for(int to: adj[v])
            if(!vis[to]){
                vis[to] = true;
                q.push(to);
                par[to] = v;
            }
    }
}

void bfs(int u){
    fill(d, d + n, INF);

    queue<int> q;
    q.push(u);
    d[u] = 0;

    while(!q.empty()){
        int v = q.front();
        q.pop();

        for(int to: adj[v])
            if(d[to] == INF){
                d[to] = d[v] + 1;
                q.push(to);
            }
    }

    /*cout << "d: ";
    for(int i = 0; i < n; ++i)
        cout << d[i] << " ";
    cout << endl;

    cout << "par: ";
    for(int i = 1; i < n; ++i)
        cout << par[i] << " ";
    cout << endl;*/

    for(int i = 1; i < n; ++i){
        encode_diff(d[i] - d[par[i]]);
    }
}

void encode(int _nv, int _nh, int _ne, int *v1, int *v2){
    n = _nv, h =_nh, m = _ne;
    for(int i = 0; i < n; ++i) adj[i].clear();
    for(int i = 0; i < m; ++i){
        adj[v1[i]].push_back(v2[i]);
        adj[v2[i]].push_back(v1[i]);
    }

    fill(vis, vis + n, false);
    bfs_0(0);
    for(int i = 1; i < n; ++i)
        encode_num(par[i]);

    for(int i = 1; i < h; ++i)
        bfs(i);

    for(int i = 0; i < en_diff.size(); i += 3){
        if(i + 2 >= en_diff.size()){
            for(; i < en_diff.size(); ++i)
                add_simple(en_diff[i]);
            continue;
        }
        
        int a1 = en_diff[i], a2 = en_diff[i + 1], a3 = en_diff[i + 2];
        ++a1, ++a2, ++a3;
        int num = a1 * 9 + a2 * 3 + a3;
        for(int j = 4; j >= 0; --j)
            encode_bit((num >> j) & 1);
    }
}

#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 1000 + 3;
const int H = 36 + 3;

static int n, h, par[N], d[N];
static vector<int> adj[N];
static bool vis[N];

int decode_diff(){
    int bit1 = decode_bit();
    int bit2 = decode_bit();
    if(bit1) return 1;
    if(bit2) return 0;
    return -1;
}

int decode_num(){
    int num = 0;
    for(int i = 9; i >= 0; --i)
        if(decode_bit())
            num += (1 << i);
    return num;
}

void dfs(int u){
    hops(0, u, d[u]);
    for(int to: adj[u]){
        if(to == par[u]) continue;
        d[to] = d[u] + 1;
        dfs(to);
    }
}

void dfs2(int hub, int u, int ans){
    hops(hub, u, ans);
    vis[u] = true;
    for(int to: adj[u])
        if(!vis[to]){
            if(to == par[u]) dfs2(hub, to, ans - d[u]);
            else dfs2(hub, to, ans + d[to]);
        }
}

void decode(int _nv, int _nh) {
    n = _nv, h = _nh;
    if(n == 1){
        hops(0, 0, 0);
        return;
    }

    for(int i = 0; i < n; ++i) adj[i].clear();
    for(int i = 1; i < n; ++i){
        par[i] = decode_num();
        adj[par[i]].push_back(i);
        adj[i].push_back(par[i]);
    }
    d[0] = 0;
    dfs(0);

    int cnt = (h - 1) * (n - 1);
    int cnt2 = cnt % 3;
    cnt = cnt / 3;

    vector<int> v;
    for(int i = 0; i < cnt; ++i){
        int num = 0;
        for(int j = 4; j >= 0; --j)
            if(decode_bit())
                num += 1 << j;
        v.push_back(num / 9 - 1);
        v.push_back(num / 3 % 3 - 1);
        v.push_back(num % 3 - 1);
    }
    for(int i = 0; i < cnt2; ++i){
        int num = 0;
        for(int j = 1; j >= 0; --j)
            if(decode_bit())
                num += (1 << j);
        num -= 1;
        v.push_back(num);
    }

    reverse(v.begin(), v.end());

    for(int i = 1; i < h; ++i){
        for(int j = 1; j < n; ++j){
            d[j] = v.back();
            v.pop_back();
        }
        fill(vis, vis + n, false);
        dfs2(i, i, 0);
    }
}

Compilation message

encoder.cpp: In function 'void encode(int, int, int, int*, int*)':
encoder.cpp:98:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for(int i = 0; i < en_diff.size(); i += 3){
      |                    ~~^~~~~~~~~~~~~~~~
encoder.cpp:99:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |         if(i + 2 >= en_diff.size()){
      |            ~~~~~~^~~~~~~~~~~~~~~~~
encoder.cpp:100:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |             for(; i < en_diff.size(); ++i)
      |                   ~~^~~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 11228 KB Output is correct - 68265 call(s) of encode_bit()
2 Correct 2 ms 4704 KB Output is correct - 54 call(s) of encode_bit()
3 Correct 31 ms 5984 KB Output is correct - 61432 call(s) of encode_bit()
4 Correct 4 ms 4704 KB Output is correct - 67 call(s) of encode_bit()
5 Correct 34 ms 6112 KB Output is correct - 61432 call(s) of encode_bit()
6 Correct 36 ms 6240 KB Output is correct - 68265 call(s) of encode_bit()
7 Correct 57 ms 6864 KB Output is correct - 68265 call(s) of encode_bit()
8 Correct 31 ms 6108 KB Output is correct - 65600 call(s) of encode_bit()
9 Correct 30 ms 6116 KB Output is correct - 68265 call(s) of encode_bit()
10 Correct 28 ms 6304 KB Output is correct - 68265 call(s) of encode_bit()
11 Correct 34 ms 6236 KB Output is correct - 68265 call(s) of encode_bit()
12 Correct 28 ms 6236 KB Output is correct - 68265 call(s) of encode_bit()
13 Correct 72 ms 6932 KB Output is correct - 68265 call(s) of encode_bit()
14 Correct 30 ms 6288 KB Output is correct - 68265 call(s) of encode_bit()
15 Correct 33 ms 6240 KB Output is correct - 68265 call(s) of encode_bit()
16 Correct 59 ms 6628 KB Output is correct - 68265 call(s) of encode_bit()
17 Correct 47 ms 6856 KB Output is correct - 68265 call(s) of encode_bit()
18 Correct 56 ms 7004 KB Output is correct - 68265 call(s) of encode_bit()
19 Correct 43 ms 6652 KB Output is correct - 68265 call(s) of encode_bit()
20 Correct 65 ms 7140 KB Output is correct - 68265 call(s) of encode_bit()
21 Correct 84 ms 7448 KB Output is correct - 68265 call(s) of encode_bit()
22 Correct 69 ms 6736 KB Output is correct - 68265 call(s) of encode_bit()
23 Correct 84 ms 7656 KB Output is correct - 68265 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 11228 KB Output is correct - 68265 call(s) of encode_bit()
2 Correct 2 ms 4704 KB Output is correct - 54 call(s) of encode_bit()
3 Correct 31 ms 5984 KB Output is correct - 61432 call(s) of encode_bit()
4 Correct 4 ms 4704 KB Output is correct - 67 call(s) of encode_bit()
5 Correct 34 ms 6112 KB Output is correct - 61432 call(s) of encode_bit()
6 Correct 36 ms 6240 KB Output is correct - 68265 call(s) of encode_bit()
7 Correct 57 ms 6864 KB Output is correct - 68265 call(s) of encode_bit()
8 Correct 31 ms 6108 KB Output is correct - 65600 call(s) of encode_bit()
9 Correct 30 ms 6116 KB Output is correct - 68265 call(s) of encode_bit()
10 Correct 28 ms 6304 KB Output is correct - 68265 call(s) of encode_bit()
11 Correct 34 ms 6236 KB Output is correct - 68265 call(s) of encode_bit()
12 Correct 28 ms 6236 KB Output is correct - 68265 call(s) of encode_bit()
13 Correct 72 ms 6932 KB Output is correct - 68265 call(s) of encode_bit()
14 Correct 30 ms 6288 KB Output is correct - 68265 call(s) of encode_bit()
15 Correct 33 ms 6240 KB Output is correct - 68265 call(s) of encode_bit()
16 Correct 59 ms 6628 KB Output is correct - 68265 call(s) of encode_bit()
17 Correct 47 ms 6856 KB Output is correct - 68265 call(s) of encode_bit()
18 Correct 56 ms 7004 KB Output is correct - 68265 call(s) of encode_bit()
19 Correct 43 ms 6652 KB Output is correct - 68265 call(s) of encode_bit()
20 Correct 65 ms 7140 KB Output is correct - 68265 call(s) of encode_bit()
21 Correct 84 ms 7448 KB Output is correct - 68265 call(s) of encode_bit()
22 Correct 69 ms 6736 KB Output is correct - 68265 call(s) of encode_bit()
23 Correct 84 ms 7656 KB Output is correct - 68265 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 11228 KB Output is correct - 68265 call(s) of encode_bit()
2 Correct 2 ms 4704 KB Output is correct - 54 call(s) of encode_bit()
3 Correct 31 ms 5984 KB Output is correct - 61432 call(s) of encode_bit()
4 Correct 4 ms 4704 KB Output is correct - 67 call(s) of encode_bit()
5 Correct 34 ms 6112 KB Output is correct - 61432 call(s) of encode_bit()
6 Correct 36 ms 6240 KB Output is correct - 68265 call(s) of encode_bit()
7 Correct 57 ms 6864 KB Output is correct - 68265 call(s) of encode_bit()
8 Correct 31 ms 6108 KB Output is correct - 65600 call(s) of encode_bit()
9 Correct 30 ms 6116 KB Output is correct - 68265 call(s) of encode_bit()
10 Correct 28 ms 6304 KB Output is correct - 68265 call(s) of encode_bit()
11 Correct 34 ms 6236 KB Output is correct - 68265 call(s) of encode_bit()
12 Correct 28 ms 6236 KB Output is correct - 68265 call(s) of encode_bit()
13 Correct 72 ms 6932 KB Output is correct - 68265 call(s) of encode_bit()
14 Correct 30 ms 6288 KB Output is correct - 68265 call(s) of encode_bit()
15 Correct 33 ms 6240 KB Output is correct - 68265 call(s) of encode_bit()
16 Correct 59 ms 6628 KB Output is correct - 68265 call(s) of encode_bit()
17 Correct 47 ms 6856 KB Output is correct - 68265 call(s) of encode_bit()
18 Correct 56 ms 7004 KB Output is correct - 68265 call(s) of encode_bit()
19 Correct 43 ms 6652 KB Output is correct - 68265 call(s) of encode_bit()
20 Correct 65 ms 7140 KB Output is correct - 68265 call(s) of encode_bit()
21 Correct 84 ms 7448 KB Output is correct - 68265 call(s) of encode_bit()
22 Correct 69 ms 6736 KB Output is correct - 68265 call(s) of encode_bit()
23 Correct 84 ms 7656 KB Output is correct - 68265 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 11228 KB Output is correct - 68265 call(s) of encode_bit()
2 Correct 2 ms 4704 KB Output is correct - 54 call(s) of encode_bit()
3 Correct 31 ms 5984 KB Output is correct - 61432 call(s) of encode_bit()
4 Correct 4 ms 4704 KB Output is correct - 67 call(s) of encode_bit()
5 Correct 34 ms 6112 KB Output is correct - 61432 call(s) of encode_bit()
6 Correct 36 ms 6240 KB Output is correct - 68265 call(s) of encode_bit()
7 Correct 57 ms 6864 KB Output is correct - 68265 call(s) of encode_bit()
8 Correct 31 ms 6108 KB Output is correct - 65600 call(s) of encode_bit()
9 Correct 30 ms 6116 KB Output is correct - 68265 call(s) of encode_bit()
10 Correct 28 ms 6304 KB Output is correct - 68265 call(s) of encode_bit()
11 Correct 34 ms 6236 KB Output is correct - 68265 call(s) of encode_bit()
12 Correct 28 ms 6236 KB Output is correct - 68265 call(s) of encode_bit()
13 Correct 72 ms 6932 KB Output is correct - 68265 call(s) of encode_bit()
14 Correct 30 ms 6288 KB Output is correct - 68265 call(s) of encode_bit()
15 Correct 33 ms 6240 KB Output is correct - 68265 call(s) of encode_bit()
16 Correct 59 ms 6628 KB Output is correct - 68265 call(s) of encode_bit()
17 Correct 47 ms 6856 KB Output is correct - 68265 call(s) of encode_bit()
18 Correct 56 ms 7004 KB Output is correct - 68265 call(s) of encode_bit()
19 Correct 43 ms 6652 KB Output is correct - 68265 call(s) of encode_bit()
20 Correct 65 ms 7140 KB Output is correct - 68265 call(s) of encode_bit()
21 Correct 84 ms 7448 KB Output is correct - 68265 call(s) of encode_bit()
22 Correct 69 ms 6736 KB Output is correct - 68265 call(s) of encode_bit()
23 Correct 84 ms 7656 KB Output is correct - 68265 call(s) of encode_bit()