Submission #975402

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
975402	2024-05-05T06:08:11 Z	LucaIlie	Mechanical Doll (IOI18_doll)	C++17	6 / 100	60 ms	15096 KB

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

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.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2648 KB	Output is correct
2	Correct	19 ms	6744 KB	Output is correct
3	Correct	14 ms	6488 KB	Output is correct
4	Correct	1 ms	2652 KB	Output is correct
5	Correct	7 ms	3932 KB	Output is correct
6	Correct	21 ms	8404 KB	Output is correct
7	Correct	1 ms	2648 KB	Output is correct

Subtask #2
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2648 KB	Output is correct
2	Correct	19 ms	6744 KB	Output is correct
3	Correct	14 ms	6488 KB	Output is correct
4	Correct	1 ms	2652 KB	Output is correct
5	Correct	7 ms	3932 KB	Output is correct
6	Correct	21 ms	8404 KB	Output is correct
7	Correct	1 ms	2648 KB	Output is correct
8	Correct	34 ms	9528 KB	Output is correct
9	Correct	38 ms	9688 KB	Output is correct
10	Correct	50 ms	13432 KB	Output is correct
11	Correct	1 ms	2652 KB	Output is correct
12	Correct	1 ms	2652 KB	Output is correct
13	Correct	1 ms	2652 KB	Output is correct

Subtask #3
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2648 KB	Output is correct
2	Correct	19 ms	6744 KB	Output is correct
3	Correct	14 ms	6488 KB	Output is correct
4	Correct	1 ms	2652 KB	Output is correct
5	Correct	7 ms	3932 KB	Output is correct
6	Correct	21 ms	8404 KB	Output is correct
7	Correct	1 ms	2648 KB	Output is correct
8	Correct	34 ms	9528 KB	Output is correct
9	Correct	38 ms	9688 KB	Output is correct
10	Correct	50 ms	13432 KB	Output is correct
11	Correct	1 ms	2652 KB	Output is correct
12	Correct	1 ms	2652 KB	Output is correct
13	Correct	1 ms	2652 KB	Output is correct
14	Incorrect	60 ms	15096 KB	state 'Y'
15	Halted	0 ms	0 KB	-