Submission #975403

#	Time	Username	Problem	Language	Result	Execution time	Memory
975403		LucaIlie	Mechanical Doll (IOI18_doll)	C++17	16 / 100	61 ms	13940 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX_M = 1e5;
const int MAX_L = (1 << 17);
int ord[MAX_L];
vector<int> adj[MAX_M + 1];

int switchid( int x ) {
    return -(x + 1);
}

void create_circuit( int m, vector<int> a ) {
    int n = a.size();

    vector<int> c( m + 1 ), x, y;

    a.push_back( 0 );
    reverse( a.begin(), a.end() );
    a.push_back( 0 );
    reverse( a.begin(), a.end() );

    for ( int i = 0; i < a.size() - 1; i++ )
        adj[a[i]].push_back( a[i + 1] );

    for ( int i = 0; i <= m; i++ ) {
        if ( adj[i].size() == 0 )
            continue;
        if ( adj[i].size() == 1 ) {
            c[i] = adj[i][0];
            continue;
        }

        int p = ceil( log2( adj[i].size() ) );
        int r = x.size();
        x.resize( r + (1 << p) - 1 );
        y.resize( r + (1 << p) - 1 );
        c[i] = switchid( r );
        for ( int v = 0; v < (1 << (p - 1)) - 1; v++ ) {
            x[r + v] = switchid( r + v * 2 + 1 );
            y[r + v] = switchid( r + v * 2 + 2 );
        }
        for ( int a = 0; a < (1 << p); a++ ) {
            int c = 0;
            for ( int b = 0; b < p; b++ ) {
                if ( (a >> b) & 1 )
                    c += (1 << (p - 1 - b));
            }
            ord[c] = a;
        }
        int ind = 0;
        for ( int j = 0; j < (1 << p); j++ ) {
            int a = ord[j];
            int v = r + (1 << (p - 1)) - 1 + a / 2;
            if ( j + 1 + adj[i].size() <= (1 << p) ) {
                if ( a % 2 == 0 )
                    x[v] = switchid( r );
                else
                    y[v] = switchid( r );
            } else {
                if ( a % 2 == 0 )
                    x[v] = adj[i][ind];
                else
                    y[v] = adj[i][ind];
                ind++;
            }
        }
    }

    answer( c, x, y );
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:25:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for ( int i = 0; i < a.size() - 1; i++ )
      |                      ~~^~~~~~~~~~~~~~
doll.cpp:57:40: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   57 |             if ( j + 1 + adj[i].size() <= (1 << p) ) {
      |                  ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
doll.cpp:16:9: warning: unused variable 'n' [-Wunused-variable]
   16 |     int n = a.size();
      |         ^

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