oj.uz

Submission #975606

# Submission time Handle Problem Language Result Execution time Memory
975606 2024-05-05T14:26:14 Z LucaIlie Mechanical Doll (IOI18_doll) C++17
84 / 100
 159 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++ ) {
        xaux[i] = switchid( nrml[idswitch( x[vert[i]] )] );
        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 37 ms 6380 KB Output is correct
3 Correct 40 ms 7496 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 7 ms 1628 KB Output is correct
6 Correct 53 ms 9788 KB Output is correct
7 Runtime error 159 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 37 ms 6380 KB Output is correct
3 Correct 40 ms 7496 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 7 ms 1628 KB Output is correct
6 Correct 53 ms 9788 KB Output is correct
7 Runtime error 159 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 37 ms 6380 KB Output is correct
3 Correct 40 ms 7496 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 7 ms 1628 KB Output is correct
6 Correct 53 ms 9788 KB Output is correct
7 Runtime error 159 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 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 604 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 1 ms 344 KB Output is correct
2 Correct 55 ms 8568 KB Output is correct
3 Correct 64 ms 10864 KB Output is correct
4 Correct 96 ms 14112 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 55 ms 8568 KB Output is correct
3 Correct 64 ms 10864 KB Output is correct
4 Correct 96 ms 14112 KB Output is correct
5 Correct 100 ms 15452 KB Output is correct
6 Correct 98 ms 16692 KB Output is correct
7 Correct 99 ms 16796 KB Output is correct
8 Correct 104 ms 16396 KB Output is correct
9 Correct 63 ms 11700 KB Output is correct
10 Correct 95 ms 16372 KB Output is correct
11 Correct 95 ms 16088 KB Output is correct
12 Correct 64 ms 12032 KB Output is correct
13 Correct 70 ms 10252 KB Output is correct
14 Correct 66 ms 12400 KB Output is correct
15 Correct 66 ms 12596 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Correct 57 ms 9924 KB Output is correct
18 Correct 66 ms 9716 KB Output is correct
19 Correct 64 ms 11952 KB Output is correct
20 Correct 96 ms 16160 KB Output is correct
21 Correct 104 ms 15920 KB Output is correct
22 Correct 96 ms 16108 KB Output is correct