oj.uz

Submission #975444

# Submission time Handle Problem Language Result Execution time Memory
975444 2024-05-05T07:57:06 Z LucaIlie Mechanical Doll (IOI18_doll) C++17
10 / 100
 1 ms 2652 KB 
#include "doll.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX_M = 1e5;
const int MAX_L = (1 << 18);
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;

    //if ( n == 16 ) {
        a.push_back( 0 );

        c[0] = a[0];

        int p = ceil( log2( n ) );
        x.resize( (1 << p) - 1 );
        y.resize( (1 << p) - 1 );
        for ( int v = 0; v < (1 << (p - 1)) - 1; v++ ) {
            x[v] = switchid( v * 2 + 1 );
            y[v] = switchid( 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;
        }
        for ( int j = 0; j < (1 << p); j++ ) {
            int b = ord[j];
            int v = (1 << (p - 1)) - 1 + b / 2;
            if ( b % 2 == 0 )
                x[v] = a[j + 1];
            else
                y[v] = a[j + 1];
        }

        for ( int i = 1; i <= m; i++ )
            c[i] = -1;
    /*} else {
        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 );
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2652 KB state 'Y'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2652 KB state 'Y'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2652 KB state 'Y'
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2652 KB state 'Y'
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2652 KB state 'Y'
2 Halted 0 ms 0 KB -