Submission #1090781

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1090781	2024-09-18T18:12:44 Z	Tymond	Saveit (IOI10_saveit)	C++17	0 / 100	152 ms	10972 KB

encoder

#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define fi first
#define se second
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

const int MAXN = 1e3 + 7;
const int MAXH = 40;
int dist[MAXH][MAXN];
int rep[MAXN];
int parent[MAXN];
vi g[MAXN];
vi gt[MAXN];
int n, h, m;

int Find(int a){
    if(a == rep[a]){
        return a;
    }
    return rep[a] = Find(rep[a]);
}

void Union(int a, int b){
    rep[Find(a)] = Find(b);
}

void dfs(int v, int p){
    parent[v] = p;
    for(auto u : g[v]){
        if(u == p){
            continue;
        }
        dfs(u, v);
    }
}

void countDist(int start){
    dist[start][start] = 0;
    queue<int> q;
    q.push(start);
    while(sz(q)){
        int v = q.front();
        q.pop();
 
        for(auto u : gt[v]){
            if(u == start){
                continue;
            }
            if(dist[start][u] == 0){
                dist[start][u] = dist[start][v] + 1;
                q.push(u);
            }
        }
    }
}

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++){
        rep[i] = i;
    }
    for(int i = 0; i < m; i++){
        if(Find(v1[i]) != Find(v2[i])){
            g[v1[i]].pb(v2[i]);
            g[v2[i]].pb(v1[i]);
            Union(v1[i], v2[i]);
        }
        gt[v1[i]].pb(v2[i]);
        gt[v2[i]].pb(v1[i]);
    }

    dfs(0, 0);
    for(int i = 1; i < n; i++){
        for(int y = 0; y < 10; y++){
            if(parent[i] & (1 << y)){
                encode_bit(1);
            }else{
                encode_bit(0);
            }
        }
    }

    for(int i = 0; i < h; i++){
        countDist(i);
    }

    for(int j = 0; j < h; j++){
        if(n % 3 != 0){
            for(int i = 0; i < n; i++){
                if(i + 2 >= n){
                    if(i == j){
                        continue;
                    }
                    if(dist[j][i] == dist[j][parent[i]]){
                        encode_bit(0);
                        encode_bit(1);
                    }else if(dist[j][i] == dist[j][parent[i]] - 1){
                        encode_bit(0);
                        encode_bit(0);
                    }else{
                        encode_bit(1);
                        encode_bit(0);
                    }
                    continue;
                }

                int r = 0;
                for(int y = i; y <= i + 2 + (j >= i && j <= i + 2); y++){
                    if(y == j){
                        continue;
                    }
                    r = r * 3 + (dist[j][y] - dist[j][parent[y]] + 1);
                }

                for(int y = 0; y < 5; y++){
                    if((1 << y) & r){
                        encode_bit(1);
                    }else{
                        encode_bit(0);
                    }
                }
                i += (j >= i && j <= i + 2);
                i += 2;
            }
            continue;
        }
        for(int i = 0; i < n; i++){
            if(i + 2 >= n){
                if(dist[j][i] == dist[j][parent[i]]){
                    encode_bit(0);
                    encode_bit(1);
                }else if(dist[j][i] == dist[j][parent[i]] - 1){
                    encode_bit(0);
                    encode_bit(0);
                }else{
                    encode_bit(1);
                    encode_bit(0);
                }
                continue;
            }

            int r = 0;
            for(int y = i; y <= i + 2; y++){
                r = r * 3 + (dist[j][y] - dist[j][parent[y]] + 1);
            }

            for(int y = 0; y < 5; y++){
                if((1 << y) & r){
                    encode_bit(1);
                }else{
                    encode_bit(0);
                }
            }
            i += 2;
        }
    }

    return;
}

decoder

#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define fi first
#define se second
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

const int MAXN = 1e3 + 7;
const int MAXH = 40;
int dist[MAXH][MAXN];
int parent[MAXN];
vi g[MAXN];
int n, h;

void decode(int nv, int nh) {
    n = nv;
    h = nh;

    for(int i = 1; i < n; i++){
        for(int y = 0; y < 10; y++){
            if(decode_bit()){
                parent[i] += (1 << y);
            }
        }
        g[parent[i]].pb(i);
    }

    for(int j = 0; j < h; j++){
        int i;
        vi vec(n, 0);
        if(n % 3 != 0){
            for(i = 0; i < n; i++){
                if(i + 2 >= n){
                    if(i == j){
                        continue;
                    }
                    int x = decode_bit();
                    int y = decode_bit();
                    vec[i] = 2 * x + y - 1;
                    continue;
                }

                int r = 0;
                for(int y = 0; y < 5; y++){
                    r += (decode_bit() * (1 << y));
                }
                for(int y = i + 2 + (j <= i + 2 && j >= i); y >= i; y--){
                    if(j == y){
                        continue;
                    }
                    vec[y] = (r % 3) - 1;
                    r /= 3;
                }

                i += (j <= i + 2 && j >= i);
                i += 2;
            }
        }else{
            for(i = 0; i < n; i++){
                if(i + 2 >= n){
                    int x = decode_bit();
                    int y = decode_bit();
                    vec[i] = 2 * x + y - 1;
                    continue;
                }

                int r = 0;
                for(int y = 0; y < 5; y++){
                    r += (decode_bit() * (1 << y));
                }
                for(int y = i + 2; y >= i; y--){
                    vec[y] = (r % 3) - 1;
                    r /= 3;
                }

                i += 2;
            }
        }

        queue<int> q;
        q.push(j);
        for(i = 0; i < n; i++){
            dist[j][i] = -1;
        }
        dist[j][j] = 0;
        while(sz(q)){
            int v = q.front();
            q.pop();

            for(auto u : g[v]){
                if(dist[j][u] == -1){
                    dist[j][u] = dist[j][v] + vec[u];
                    q.push(u);
                } 
            }

            if(dist[j][parent[v]] == -1){
                q.push(parent[v]);
                dist[j][parent[v]] = dist[j][v] - vec[v];
            }
        }
    }

    for(int i = 0; i < h; i++){
        for(int j = 0; j < n; j++){
            hops(i, j, dist[i][j]);
        }
    }

    return;
}

Subtask #1

0.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	152 ms	10972 KB	Output isn't correct
2	Incorrect	2 ms	4628 KB	Output isn't correct
3	Correct	14 ms	5900 KB	Output is correct - 62990 call(s) of encode_bit()
4	Incorrect	2 ms	4624 KB	Output isn't correct
5	Correct	18 ms	6036 KB	Output is correct - 62990 call(s) of encode_bit()
6	Incorrect	16 ms	6020 KB	Output isn't correct
7	Incorrect	27 ms	6372 KB	Output isn't correct
8	Incorrect	16 ms	5908 KB	Output isn't correct
9	Incorrect	16 ms	5892 KB	Output isn't correct
10	Incorrect	15 ms	5908 KB	Output isn't correct
11	Incorrect	19 ms	5896 KB	Output isn't correct
12	Incorrect	24 ms	5900 KB	Output isn't correct
13	Incorrect	37 ms	6360 KB	Output isn't correct
14	Incorrect	20 ms	6068 KB	Output isn't correct
15	Incorrect	14 ms	5832 KB	Output isn't correct
16	Incorrect	39 ms	6516 KB	Output isn't correct
17	Incorrect	30 ms	6476 KB	Output isn't correct
18	Incorrect	34 ms	6684 KB	Output isn't correct
19	Incorrect	25 ms	6308 KB	Output isn't correct
20	Incorrect	45 ms	6776 KB	Output isn't correct
21	Incorrect	56 ms	6928 KB	Output isn't correct
22	Incorrect	32 ms	6756 KB	Output isn't correct
23	Incorrect	49 ms	7432 KB	Output isn't correct

Subtask #2

0.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	152 ms	10972 KB	Output isn't correct
2	Incorrect	2 ms	4628 KB	Output isn't correct
3	Correct	14 ms	5900 KB	Output is correct - 62990 call(s) of encode_bit()
4	Incorrect	2 ms	4624 KB	Output isn't correct
5	Correct	18 ms	6036 KB	Output is correct - 62990 call(s) of encode_bit()
6	Incorrect	16 ms	6020 KB	Output isn't correct
7	Incorrect	27 ms	6372 KB	Output isn't correct
8	Incorrect	16 ms	5908 KB	Output isn't correct
9	Incorrect	16 ms	5892 KB	Output isn't correct
10	Incorrect	15 ms	5908 KB	Output isn't correct
11	Incorrect	19 ms	5896 KB	Output isn't correct
12	Incorrect	24 ms	5900 KB	Output isn't correct
13	Incorrect	37 ms	6360 KB	Output isn't correct
14	Incorrect	20 ms	6068 KB	Output isn't correct
15	Incorrect	14 ms	5832 KB	Output isn't correct
16	Incorrect	39 ms	6516 KB	Output isn't correct
17	Incorrect	30 ms	6476 KB	Output isn't correct
18	Incorrect	34 ms	6684 KB	Output isn't correct
19	Incorrect	25 ms	6308 KB	Output isn't correct
20	Incorrect	45 ms	6776 KB	Output isn't correct
21	Incorrect	56 ms	6928 KB	Output isn't correct
22	Incorrect	32 ms	6756 KB	Output isn't correct
23	Incorrect	49 ms	7432 KB	Output isn't correct

Subtask #3

0.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	152 ms	10972 KB	Output isn't correct
2	Incorrect	2 ms	4628 KB	Output isn't correct
3	Correct	14 ms	5900 KB	Output is correct - 62990 call(s) of encode_bit()
4	Incorrect	2 ms	4624 KB	Output isn't correct
5	Correct	18 ms	6036 KB	Output is correct - 62990 call(s) of encode_bit()
6	Incorrect	16 ms	6020 KB	Output isn't correct
7	Incorrect	27 ms	6372 KB	Output isn't correct
8	Incorrect	16 ms	5908 KB	Output isn't correct
9	Incorrect	16 ms	5892 KB	Output isn't correct
10	Incorrect	15 ms	5908 KB	Output isn't correct
11	Incorrect	19 ms	5896 KB	Output isn't correct
12	Incorrect	24 ms	5900 KB	Output isn't correct
13	Incorrect	37 ms	6360 KB	Output isn't correct
14	Incorrect	20 ms	6068 KB	Output isn't correct
15	Incorrect	14 ms	5832 KB	Output isn't correct
16	Incorrect	39 ms	6516 KB	Output isn't correct
17	Incorrect	30 ms	6476 KB	Output isn't correct
18	Incorrect	34 ms	6684 KB	Output isn't correct
19	Incorrect	25 ms	6308 KB	Output isn't correct
20	Incorrect	45 ms	6776 KB	Output isn't correct
21	Incorrect	56 ms	6928 KB	Output isn't correct
22	Incorrect	32 ms	6756 KB	Output isn't correct
23	Incorrect	49 ms	7432 KB	Output isn't correct

Subtask #4

0.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	152 ms	10972 KB	Output isn't correct
2	Incorrect	2 ms	4628 KB	Output isn't correct
3	Correct	14 ms	5900 KB	Output is correct - 62990 call(s) of encode_bit()
4	Incorrect	2 ms	4624 KB	Output isn't correct
5	Correct	18 ms	6036 KB	Output is correct - 62990 call(s) of encode_bit()
6	Incorrect	16 ms	6020 KB	Output isn't correct
7	Incorrect	27 ms	6372 KB	Output isn't correct
8	Incorrect	16 ms	5908 KB	Output isn't correct
9	Incorrect	16 ms	5892 KB	Output isn't correct
10	Incorrect	15 ms	5908 KB	Output isn't correct
11	Incorrect	19 ms	5896 KB	Output isn't correct
12	Incorrect	24 ms	5900 KB	Output isn't correct
13	Incorrect	37 ms	6360 KB	Output isn't correct
14	Incorrect	20 ms	6068 KB	Output isn't correct
15	Incorrect	14 ms	5832 KB	Output isn't correct
16	Incorrect	39 ms	6516 KB	Output isn't correct
17	Incorrect	30 ms	6476 KB	Output isn't correct
18	Incorrect	34 ms	6684 KB	Output isn't correct
19	Incorrect	25 ms	6308 KB	Output isn't correct
20	Incorrect	45 ms	6776 KB	Output isn't correct
21	Incorrect	56 ms	6928 KB	Output isn't correct
22	Incorrect	32 ms	6756 KB	Output isn't correct
23	Incorrect	49 ms	7432 KB	Output isn't correct