Submission #1238823

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238823		cjoa	Mechanical Doll (IOI18_doll)	C++20	53 / 100	123 ms	35468 KiB

doll

#include "doll.h"
 
#include <bits/stdc++.h>
 
using namespace std;
 
void sub_form_array(int log2, vector<int> &arr, unordered_map<int, int> &idx)
{
    
    arr[0] = 1;
    for( int i = 1; i < (1<<log2) ; ++i )
    {
        // cerr << i*2 << " :IDX ARR: " << arr[i*2] << '\n';
        if ( i%2 )
            arr[i*2] = arr[i*2 - 2] + (1<<log2);
        else 
        {
            int divisible_by = (1<<log2);
            while ( i % divisible_by )
                divisible_by/=2;
            
            if ( i*2 >= divisible_by*2 && arr[ i*2 - divisible_by ] > arr[ i*2 - divisible_by*2 ] )
            {
                arr[i*2] = arr[ i*2 - divisible_by ] - (1<<log2) / divisible_by;
            }
            else
                arr[i*2] = arr[ i*2 - divisible_by ] + (1<<log2) / divisible_by*2;
        }
        idx[arr[i*2]] = i*2;
        // cerr << i*2 << " :IDX ARR: " << arr[i*2] << '\n';
    }
 
        // for ( const int &a : arr )
        // cerr << a << ' ';
        // cerr << '\n';
    for ( int i = (1<<log2+1); i < arr.size(); i += 2 )
    {
        arr[i] = arr[i - (1<<log2+1)] + 1;
        idx[arr[i]] = i;
    }
 
    // for ( const int &a : arr )
    //     cerr << a << ' ';
}
 
vector<int> form_array( vector<int> d_adj )
{
    unordered_map< int, int > idx;
    int log2 = static_cast<int> ( log( (double)(d_adj.size()-1) ) / log ( 2 ) ) - 1; // static_cast seems better than implicit cast
    int _2log = ( 1 << (log2 + 1) );
    vector<int> arr( ( _2log*2 ) );
 
    sub_form_array(log2, arr, idx);
    
    int offset = d_adj.size() - _2log + 1;
    for ( int n = _2log; n >= 1; --n )
    {
        int i = idx[n]+1;
        int *a = &arr[ i ];
        if ( 0 < (--offset) )
            *a = ( _2log + offset );
        else
        {
            *a = -1;
        }
    }
 
    return arr;
}
 
 
int s_count = 0;
vector < int > C, X, Y;
unordered_map < int, int > parent;
 
int get_global_parent(int idx )
{
    //assert(parent[idx] != 0);
    if ( parent[idx] > 0 )
    {
        return idx;
    }
    
    return get_global_parent( parent[idx] );
}
 
void recursive_magic(int idx, int count, int arr_idx, vector<int> &arr, vector<int> &d_adj)
{
    if ( idx > 0 )
    {
        ++s_count;
        parent[-s_count] = idx;
        C[idx] = -s_count;
        recursive_magic(-(s_count), count, arr_idx, arr, d_adj);
        return;
    }
    X.push_back(0), Y.push_back(0);
 
    if ( count == 2 ) // count will always reach 2 as count is always a power of 2
    {
        int a1 = arr[arr_idx];
        int a2 = arr[arr_idx+1];
        X[-idx - 1] = (a1 > 0? d_adj[a1-1] : get_global_parent(idx ));
        Y[-idx - 1] = (a2 > 0? d_adj[a2-1] : get_global_parent(idx ));
        return;
    }
 
    //assert(count >= 2);
    int tmp = count/2;
    int mid = arr_idx + tmp;
 
    ++s_count;
    parent[-s_count] = idx;
    X[-idx - 1] = -s_count;
    recursive_magic(-(s_count), tmp, arr_idx, arr, d_adj);
 
    ++s_count;
    parent[-s_count] = idx;
    Y[-idx - 1] = -s_count;
    recursive_magic(-(s_count), tmp, mid, arr, d_adj);
}
 
void create_circuit(int M, vector<int> A)
{
    vector< vector<int> > directed_adj(M+1);
    C.resize(M+1);
    C[0] = A[0];
 
    A.push_back(0);
    for ( int _ = 0; _ < A.size()-1; ++_ )
    {
        directed_adj[ A[_] ].push_back( A[_+1] ); // I'll convert everything to a directed graph and make switches based on that
    }
 
    for ( int i = 1; i <= M; ++i )
    {
        if ( directed_adj[i].empty() )
            continue;
        else if ( directed_adj[i].size() == 1)
        {
            C[i] = directed_adj[i][0];
            continue;
        }
        vector<int> arr = form_array( directed_adj[i] );
        recursive_magic(i, arr.size(), 0, arr, directed_adj[i]);
    }
 
    // cerr << C.size() << '\n';
    // for ( int i = 0; i < C.size(); ++i )
    //     cerr << C[i] << " :C | A: " << A[i] << '\n';
    // cerr << X.size() << '\n';
    // for ( int i = 0; i < X.size(); ++i )
    //     cerr << X[i] << " :X | Y: " << Y[i] << '\n';
    answer(C, X, Y);
    return;
}

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 9 / 18
• Subtask 6: 28 / 56