oj.uz

Submission #794054

# Submission time Handle Problem Language Result Execution time Memory
794054 2023-07-26T08:59:09 Z fatemetmhr Mechanical Doll (IOI18_doll) C++17
53 / 100
 141 ms 73568 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});
                av[i].pb({newnode + 1, 0});
                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);
        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 13 ms 23764 KB Output is correct
2 Correct 32 ms 27932 KB Output is correct
3 Correct 31 ms 27512 KB Output is correct
4 Correct 12 ms 23684 KB Output is correct
5 Correct 20 ms 24956 KB Output is correct
6 Correct 36 ms 29372 KB Output is correct
7 Correct 14 ms 23764 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 32 ms 27932 KB Output is correct
3 Correct 31 ms 27512 KB Output is correct
4 Correct 12 ms 23684 KB Output is correct
5 Correct 20 ms 24956 KB Output is correct
6 Correct 36 ms 29372 KB Output is correct
7 Correct 14 ms 23764 KB Output is correct
8 Correct 49 ms 30324 KB Output is correct
9 Correct 49 ms 31056 KB Output is correct
10 Correct 68 ms 33836 KB Output is correct
11 Correct 12 ms 23776 KB Output is correct
12 Correct 12 ms 23760 KB Output is correct
13 Correct 12 ms 23764 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 32 ms 27932 KB Output is correct
3 Correct 31 ms 27512 KB Output is correct
4 Correct 12 ms 23684 KB Output is correct
5 Correct 20 ms 24956 KB Output is correct
6 Correct 36 ms 29372 KB Output is correct
7 Correct 14 ms 23764 KB Output is correct
8 Correct 49 ms 30324 KB Output is correct
9 Correct 49 ms 31056 KB Output is correct
10 Correct 68 ms 33836 KB Output is correct
11 Correct 12 ms 23776 KB Output is correct
12 Correct 12 ms 23760 KB Output is correct
13 Correct 12 ms 23764 KB Output is correct
14 Correct 84 ms 36780 KB Output is correct
15 Incorrect 51 ms 30140 KB wrong motion
16 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23784 KB Output is correct
2 Correct 12 ms 23736 KB Output is correct
3 Correct 12 ms 23768 KB Output is correct
4 Correct 12 ms 23720 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 13 ms 23760 KB Output is correct
7 Correct 12 ms 23840 KB Output is correct
8 Correct 12 ms 23764 KB Output is correct

Subtask #5
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 12 ms 23788 KB Output is partially correct
2 Correct 71 ms 48280 KB Output is correct
3 Partially correct 111 ms 68668 KB Output is partially correct
4 Partially correct 124 ms 72228 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 12 ms 23788 KB Output is partially correct
2 Correct 71 ms 48280 KB Output is correct
3 Partially correct 111 ms 68668 KB Output is partially correct
4 Partially correct 124 ms 72228 KB Output is partially correct
5 Partially correct 129 ms 73568 KB Output is partially correct
6 Partially correct 126 ms 73084 KB Output is partially correct
7 Partially correct 129 ms 73224 KB Output is partially correct
8 Partially correct 141 ms 72956 KB Output is partially correct
9 Partially correct 120 ms 68712 KB Output is partially correct
10 Partially correct 124 ms 72856 KB Output is partially correct
11 Partially correct 125 ms 72644 KB Output is partially correct
12 Partially correct 122 ms 68964 KB Output is partially correct
13 Correct 73 ms 48812 KB Output is correct
14 Partially correct 117 ms 69236 KB Output is partially correct
15 Partially correct 122 ms 69320 KB Output is partially correct
16 Partially correct 15 ms 24984 KB Output is partially correct
17 Correct 72 ms 48564 KB Output is correct
18 Correct 76 ms 48488 KB Output is correct
19 Partially correct 121 ms 68912 KB Output is partially correct
20 Partially correct 123 ms 72768 KB Output is partially correct
21 Partially correct 131 ms 72656 KB Output is partially correct
22 Partially correct 126 ms 72716 KB Output is partially correct