oj.uz

Submission #796078

# Submission time Handle Problem Language Result Execution time Memory
796078 2023-07-28T05:52:33 Z fatemetmhr Mechanical Doll (IOI18_doll) C++17
10 / 100
 69 ms 17772 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, ind[maxn5], sz[maxn5], need = 0, val[maxn5];
vector <int> c, x, y, tmp1, tmp2, adj1, adj2;
vector <pair<int, pair<int, int>>> av;

void build(int lev){
    tmp1.clear();
    tmp1.pb(0);
    newnode = 1;
    adj1.pb(0); adj2.pb(0);
    lev--;
    for(int i = 0; i < lev; i++){
        tmp2.clear();
        for(auto u : tmp1)
            tmp2.pb(u);
        tmp1.clear();
        for(auto u : tmp2){
            tmp1.pb(newnode);
            tmp1.pb(newnode + 1);
            val[newnode] = val[u];
            val[newnode + 1] = val[u] + (1 << i);
            adj1[u] = newnode++;
            adj2[u] = newnode++;
            adj1.pb(0); adj1.pb(0);
            adj2.pb(0); adj2.pb(0);
        }
    }
}

void dfs(int v){
    if(adj1[v] == 0){
        if(need > 2){
            sz[v] = 0;
            need -= 2;
            adj1[v] = adj2[v] = -1;
        }
        else if(need == 1){
            sz[v] = 1;
            need--;
            adj1[v] = -1;
        }
        else
            sz[v] = 2;
        return;
    }
    dfs(adj1[v]);
    dfs(adj2[v]);
    sz[v] = sz[adj1[v]] + sz[adj2[v]];
    if(!sz[adj1[v]])
        adj1[v] = -1;
    if(!sz[adj2[v]])
        adj2[v] = -1;
}

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 lg = 1;
    while((1 << lg) < n)
        lg++;
    build(lg);
    need = (1 << lg) - n;
    dfs(0);
    av.clear();
    int id = 0;
    /*
    for(int i = 0; i < newnode; i++)
        cout << i << ' ' << sz[i] << ' ' << adj1[i] << ' ' << adj2[i] << endl;
    //*/
    for(int i = 0; i < newnode; i++) if(sz[i]){
        x.pb(0);
        y.pb(0);
        ind[i] = id++;
    }
    for(int i = 0; i < newnode; i++) if(sz[i]){
        if(adj1[i] > 0)
            x[ind[i]] = -(1 + ind[adj1[i]]);
        else if(adj1[i] == 0)
            av.pb({val[i], {ind[i], 0}});
        else
            x[ind[i]] = -1;
        if(adj2[i] > 0)
            y[ind[i]] = -(1 + ind[adj2[i]]);
        else if(adj2[i] == 0)
            av.pb({val[i] + (1 << (lg - 1)), {ind[i], 1}});
        else
            y[ind[i]] = -1;    
    }
    sort(all(av));

    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[i].se.se)
            y[av[i].se.fi] = a[i + 1];
        else
            x[av[i].se.fi] = a[i + 1];
    }
    answer(c, x, y);    
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 27 ms 7260 KB Output is correct
3 Correct 25 ms 8508 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 8 ms 1612 KB Output is correct
6 Incorrect 40 ms 11172 KB state 'Y'
7 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 27 ms 7260 KB Output is correct
3 Correct 25 ms 8508 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 8 ms 1612 KB Output is correct
6 Incorrect 40 ms 11172 KB state 'Y'
7 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 27 ms 7260 KB Output is correct
3 Correct 25 ms 8508 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 8 ms 1612 KB Output is correct
6 Incorrect 40 ms 11172 KB state 'Y'
7 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 44 ms 10768 KB Output is correct
3 Correct 41 ms 13868 KB Output is correct
4 Incorrect 69 ms 17772 KB state 'Y'
5 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 44 ms 10768 KB Output is correct
3 Correct 41 ms 13868 KB Output is correct
4 Incorrect 69 ms 17772 KB state 'Y'
5 Halted 0 ms 0 KB -