oj.uz

Submission #794068

# Submission time Handle Problem Language Result Execution time Memory
794068 2023-07-26T09:05:03 Z fatemetmhr Mechanical Doll (IOI18_doll) C++17
63 / 100
 131 ms 73616 KB 
#include "doll.h"
#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define mp     make_pair
#define fi     first
#define se     second
#define pb     push_back

typedef long long ll;

const int maxn5 = 1e6 + 10;

int newnode = 0, pt[maxn5], cnt[maxn5];
vector <int> c, x, y;
vector <pair<int, int>> av[maxn5];

int build(int n){
    int rt = newnode++;
    x.pb(0);
    y.pb(0);
    if(n == 2){
        av[rt].pb({rt, 0});
        av[rt].pb({rt, 1});
        return rt;
    }
    int a = (n / 2);
    if(n & 1)
        a++;
    int r1 = build(a), r2 = build(a);
    x[rt] = -(r1 + 1);
    y[rt] = -(r2 + 1);
    //cout << "building " << n << ' ' << rt << ' ' << r1 << ' ' << r2 << ' ' << newnode << endl;
    for(int i = 0; i < a; i++){
        if(n % 2 && i == a - 1){
            if(av[r1][i].se)
                y[av[r1][i].fi] = -(rt + 1);
            else
                x[av[r1][i].fi] = -(rt + 1);
        }
        else
            av[rt].pb(av[r1][i]);
        av[rt].pb(av[r2][i]);
    }
    /*
    for(auto [u, v] : av[rt])
        cout << u << ' ' << v << endl;
    cout << "done " << x[rt] << ' ' << y[rt] << endl;
    //*/
    return rt;
}


void create_circuit(int m, std::vector<int> a) {
    int n = a.size();
    if(n == 1){
        c.pb(a[0]);
        for(int i = 0; i < m; i++)
            c.pb(0);
        answer(c, x, y);
        return;
    }
    int mx = 0;
    for(int i = 0; i < n; i++){
        cnt[a[i]]++;
        mx = max(mx, cnt[a[i]]);
    }
    if(mx <= 4){
        a.pb(0);
        c.resize(m + 1);
        c[0] = a[0];
        for(int i = 1; i <= m; i++){
            if(cnt[i] == 1)
                av[i].pb({-i, 0});
            if(cnt[i] == 2){
                c[i] = -(newnode + 1);
                av[i].pb({newnode, 0});
                av[i].pb({newnode, 1});
                newnode++;
                x.pb(0);
                y.pb(0);
            }
            if(cnt[i] == 3){
                c[i] = -(newnode + 1);
                newnode++;
                x.pb(-(newnode + 1));
                y.pb(-(newnode + 2));
                x.pb(0); x.pb(0);
                y.pb(c[i]); y.pb(0);
                av[i].pb({newnode, 0});
                av[i].pb({newnode + 1, 0});
                av[i].pb({newnode + 1, 1});
                newnode += 2;
            }
            if(cnt[i] == 4){
                c[i] = -(newnode + 1);
                newnode++;
                x.pb(-(newnode + 1));
                y.pb(-(newnode + 2));
                x.pb(0); x.pb(0);
                y.pb(0); y.pb(0);
                av[i].pb({newnode, 0});
                av[i].pb({newnode + 1, 0});
                av[i].pb({newnode, 1});
                av[i].pb({newnode + 1, 1});
                newnode += 2;
            }
        }

        for(int i = 0; i < n; i++){
            if(cnt[a[i]] == 1)
                c[a[i]] = a[i + 1];
            else{
                int u = a[i];
                if(av[u][pt[u]].se)
                    y[av[u][pt[u]].fi] = a[i + 1];
                else
                    x[av[u][pt[u]].fi] = a[i + 1];
                pt[u]++;
            }
        }
        answer(c, x, y);
        /*
        for(int i = 0; i < c.size(); i++)
            cout << c[i] << ' ';
        cout << endl;
        for(int i = 0; i < x.size(); i++)
            cout << x[i] << ' ' << y[i] << endl;
            //*/
        return;
    }

    build(n);
    c.pb(a[0]);
    for(int i = 0; i < m; i++)
        c.pb(-1);
    a.pb(0);
    for(int i = 0; i < n; i++){
        if(av[0][i].se)
            y[av[0][i].fi] = a[i + 1];
        else
            x[av[0][i].fi] = a[i + 1];
    }
    answer(c, x, y);
    /*
    for(auto u : c)
        cout << u << ' ';
    cout << endl;
    for(int i = 0; i < x.size(); i++)
        cout << x[i] << ' ' << y[i] << endl;
    //*/
    return;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23764 KB Output is correct
2 Correct 26 ms 27856 KB Output is correct
3 Correct 30 ms 27460 KB Output is correct
4 Correct 10 ms 23724 KB Output is correct
5 Correct 19 ms 25044 KB Output is correct
6 Correct 46 ms 29380 KB Output is correct
7 Correct 13 ms 23816 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23764 KB Output is correct
2 Correct 26 ms 27856 KB Output is correct
3 Correct 30 ms 27460 KB Output is correct
4 Correct 10 ms 23724 KB Output is correct
5 Correct 19 ms 25044 KB Output is correct
6 Correct 46 ms 29380 KB Output is correct
7 Correct 13 ms 23816 KB Output is correct
8 Correct 47 ms 30376 KB Output is correct
9 Correct 42 ms 31108 KB Output is correct
10 Correct 63 ms 33864 KB Output is correct
11 Correct 16 ms 23732 KB Output is correct
12 Correct 13 ms 23688 KB Output is correct
13 Correct 11 ms 23764 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23764 KB Output is correct
2 Correct 26 ms 27856 KB Output is correct
3 Correct 30 ms 27460 KB Output is correct
4 Correct 10 ms 23724 KB Output is correct
5 Correct 19 ms 25044 KB Output is correct
6 Correct 46 ms 29380 KB Output is correct
7 Correct 13 ms 23816 KB Output is correct
8 Correct 47 ms 30376 KB Output is correct
9 Correct 42 ms 31108 KB Output is correct
10 Correct 63 ms 33864 KB Output is correct
11 Correct 16 ms 23732 KB Output is correct
12 Correct 13 ms 23688 KB Output is correct
13 Correct 11 ms 23764 KB Output is correct
14 Correct 67 ms 36808 KB Output is correct
15 Correct 54 ms 30224 KB Output is correct
16 Correct 66 ms 33720 KB Output is correct
17 Correct 15 ms 23804 KB Output is correct
18 Correct 12 ms 23728 KB Output is correct
19 Correct 15 ms 23800 KB Output is correct
20 Correct 68 ms 35232 KB Output is correct
21 Correct 11 ms 23764 KB Output is correct
22 Correct 12 ms 23764 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23728 KB Output is correct
2 Correct 13 ms 23704 KB Output is correct
3 Correct 10 ms 23764 KB Output is correct
4 Correct 11 ms 23728 KB Output is correct
5 Correct 10 ms 23744 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 11 ms 23896 KB Output is correct
8 Correct 12 ms 23768 KB Output is correct

Subtask #5
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 9 ms 23680 KB Output is partially correct
2 Correct 65 ms 48284 KB Output is correct
3 Partially correct 113 ms 68620 KB Output is partially correct
4 Partially correct 117 ms 72328 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 9 ms 23680 KB Output is partially correct
2 Correct 65 ms 48284 KB Output is correct
3 Partially correct 113 ms 68620 KB Output is partially correct
4 Partially correct 117 ms 72328 KB Output is partially correct
5 Partially correct 112 ms 73616 KB Output is partially correct
6 Partially correct 119 ms 73168 KB Output is partially correct
7 Partially correct 126 ms 73124 KB Output is partially correct
8 Partially correct 109 ms 72968 KB Output is partially correct
9 Partially correct 131 ms 68612 KB Output is partially correct
10 Partially correct 117 ms 72924 KB Output is partially correct
11 Partially correct 126 ms 72696 KB Output is partially correct
12 Partially correct 124 ms 68972 KB Output is partially correct
13 Correct 63 ms 48864 KB Output is correct
14 Partially correct 105 ms 69256 KB Output is partially correct
15 Partially correct 102 ms 69312 KB Output is partially correct
16 Partially correct 13 ms 25044 KB Output is partially correct
17 Correct 61 ms 48620 KB Output is correct
18 Correct 63 ms 48556 KB Output is correct
19 Partially correct 108 ms 68844 KB Output is partially correct
20 Partially correct 118 ms 72932 KB Output is partially correct
21 Partially correct 109 ms 72536 KB Output is partially correct
22 Partially correct 112 ms 72596 KB Output is partially correct