oj.uz

Submission #975610

# Submission time Handle Problem Language Result Execution time Memory
975610 2024-05-05T14:33:54 Z LucaIlie Mechanical Doll (IOI18_doll) C++17
84 / 100
 154 ms 262144 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> c, x, y;
int switchid( int x ) {
    return -(x + 1);
}
int idswitch( int x ) {
    return -(x + 1);
}


vector<int> vert;
vector<pair<int, int>> leafs;
int P;

void dfs( int v, int s, int l, bool canCut ) {
    vert.push_back( v );
    if ( canCut && ((s >> l) & 1) ) {
        x[v] = -1;
        if ( l == 0 ) {
            leafs.push_back( { v, 1 } );
            return;
        }
        dfs( v * 2 + 2, s, l - 1, canCut );
        return;
    }
    if ( l == 0 ) {
        leafs.push_back( { v, 0 } );
        leafs.push_back( { v, 1 } );
        return;
    }
    dfs( v * 2 + 1, s, l - 1, canCut );
    dfs( v * 2 + 2, s, l - 1, false );
}

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

    c.resize( m + 1 );
    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 v = 0; v < (1 << p); v++ ) {
        int c = 0;
        for ( int b = 0; b < p; b++ ) {
            if ((v >> b) & 1 )
                c += (1 << (p - 1 - b));
        }
        ord[v] = c;
    }

    dfs( 0, (1 << p) - n, p - 1, true );

    for ( int i = 1; i <= m; i++ )
        c[i] = -1;

    vector<int> nrml( x.size() );
    for ( int v = 0; v < x.size(); v++ )
        nrml[v] = -1;
    sort( vert.begin(), vert.end() );
    for ( int i = 0; i < vert.size(); i++ )
        nrml[vert[i]] = i;
    vector<int> xaux( vert.size() ), yaux( vert.size() );
    for ( int i = 0; i < vert.size(); i++ ) {
        if ( x[vert[i]] != 0 )
            xaux[i] = switchid( nrml[idswitch( x[vert[i]] )] );
        if ( y[vert[i]] != 0 )
            yaux[i] = switchid( nrml[idswitch( y[vert[i]] )] );
    }

    P = p;
    sort( leafs.begin(), leafs.end(), []( auto c, auto d ) {
        return ord[(c.first - (1 << (P - 1)) + 1) * 2 + c.second] < ord[(d.first - (1 << (P - 1)) + 1) * 2 + d.second];
    } );

    int ind = 1;
    for ( auto leaf: leafs ) {
        int v = nrml[leaf.first];
        if ( leaf.second == 0 )
            xaux[v] = a[ind];
        else
            yaux[v] = a[ind];
        ind++;
    }

    answer( c, xaux, yaux );
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:72:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for ( int v = 0; v < x.size(); v++ )
      |                      ~~^~~~~~~~~~
doll.cpp:75:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for ( int i = 0; i < vert.size(); i++ )
      |                      ~~^~~~~~~~~~~~~
doll.cpp:78:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for ( int i = 0; i < vert.size(); i++ ) {
      |                      ~~^~~~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 33 ms 5932 KB Output is correct
3 Correct 37 ms 6984 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 7 ms 1492 KB Output is correct
6 Correct 53 ms 9280 KB Output is correct
7 Runtime error 154 ms 262144 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 33 ms 5932 KB Output is correct
3 Correct 37 ms 6984 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 7 ms 1492 KB Output is correct
6 Correct 53 ms 9280 KB Output is correct
7 Runtime error 154 ms 262144 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 33 ms 5932 KB Output is correct
3 Correct 37 ms 6984 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 7 ms 1492 KB Output is correct
6 Correct 53 ms 9280 KB Output is correct
7 Runtime error 154 ms 262144 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 54 ms 8664 KB Output is correct
3 Correct 66 ms 10708 KB Output is correct
4 Correct 92 ms 14124 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 54 ms 8664 KB Output is correct
3 Correct 66 ms 10708 KB Output is correct
4 Correct 92 ms 14124 KB Output is correct
5 Correct 102 ms 15528 KB Output is correct
6 Correct 96 ms 15272 KB Output is correct
7 Correct 96 ms 15240 KB Output is correct
8 Correct 96 ms 14928 KB Output is correct
9 Correct 66 ms 10872 KB Output is correct
10 Correct 110 ms 14760 KB Output is correct
11 Correct 93 ms 14488 KB Output is correct
12 Correct 62 ms 11120 KB Output is correct
13 Correct 57 ms 9272 KB Output is correct
14 Correct 65 ms 11508 KB Output is correct
15 Correct 66 ms 11692 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Correct 56 ms 8904 KB Output is correct
18 Correct 57 ms 9004 KB Output is correct
19 Correct 67 ms 10964 KB Output is correct
20 Correct 94 ms 14640 KB Output is correct
21 Correct 105 ms 14412 KB Output is correct
22 Correct 93 ms 14640 KB Output is correct