oj.uz

Submission #228707

# Submission time Handle Problem Language Result Execution time Memory
228707 2020-05-02T11:37:53 Z DodgeBallMan Mechanical Doll (IOI18_doll) C++14
100 / 100
 154 ms 10788 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
 
const int N = 3e5+5;
int lef[N], rig[N], arr[N], vis[N], cnt, pos;
 
int build( int l, int r ) {
    if( l == r ) return l;
    int mid = l + r >> 1, cur = ++cnt;
    lef[cur] = build( l, mid );
    rig[cur] = build( mid+1, r );
    //printf("build: l = %d, r = %d\n", l, r);
    //printf("switch = %d, lef = %d, rig = %d\n", -cur, lef[cur], rig[cur]);
    return -cur;
}
 
int fix( int num, int lim, int j ) {
    int cur = ++cnt;
    if ( num & ( 1<<j ) ) lef[cur] = build(lim+1, lim+(1<<j)), num -= (1<<j), lim += (1<<j);
    else lef[cur] = -1;
    if( j == 0 ) rig[cur] = 0;
    else rig[cur] = fix( num, lim, j-1 );
    //printf("fix: j = %d\n", j);
    //printf("cur = %d, lef = %d, rig = %d\n", -cur, lef[cur], rig[cur]);
    return -cur;
}
 
void create_circuit( int m, vector<int> A ) {
    int n = A.size();
    for( int i = 1 ; i <= n ; i++ ) arr[i] = A[i-1];
    int j = 0;
    while ( ( 1 << j ) <= n ) j++;
    vector<int> C( m+1 );
    C[0] = fix( n, 0, j-1 );
    for( int i = 1 ; i <= m ; i++ ) C[i] = C[0];
    int cur = -1;
    while( cur != 0 ){
        if( !vis[-cur] ){
            vis[-cur] ^= 1;
            if( lef[-cur] >= 1 ) lef[-cur] = arr[++pos], cur = C[0];
            else cur = lef[-cur];
        }
        else{
            vis[-cur] ^= 1;
            if( rig[-cur] >= 1 ) rig[-cur] = arr[++pos], cur = C[0];
            else cur = rig[-cur];
        }
    }

    vector<int> x, y;
    for ( int i = 0; i < cnt; i++ ) x.emplace_back( lef[i+1] ), y.emplace_back( rig[i+1] );
    answer( C, x, y );
}

Compilation message

doll.cpp: In function 'int build(int, int)':
doll.cpp:10:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   10 |     int mid = l + r >> 1, cur = ++cnt;
      |               ~~^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 51 ms 4552 KB Output is correct
3 Correct 46 ms 4152 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 14 ms 1484 KB Output is correct
6 Correct 68 ms 6328 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 51 ms 4552 KB Output is correct
3 Correct 46 ms 4152 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 14 ms 1484 KB Output is correct
6 Correct 68 ms 6328 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 86 ms 7316 KB Output is correct
9 Correct 95 ms 7688 KB Output is correct
10 Correct 136 ms 10788 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 51 ms 4552 KB Output is correct
3 Correct 46 ms 4152 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 14 ms 1484 KB Output is correct
6 Correct 68 ms 6328 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 86 ms 7316 KB Output is correct
9 Correct 95 ms 7688 KB Output is correct
10 Correct 136 ms 10788 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 131 ms 10396 KB Output is correct
15 Correct 100 ms 7072 KB Output is correct
16 Correct 154 ms 10416 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 132 ms 10536 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 2 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 82 ms 6448 KB Output is correct
3 Correct 78 ms 6460 KB Output is correct
4 Correct 127 ms 9844 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 82 ms 6448 KB Output is correct
3 Correct 78 ms 6460 KB Output is correct
4 Correct 127 ms 9844 KB Output is correct
5 Correct 145 ms 10132 KB Output is correct
6 Correct 127 ms 9944 KB Output is correct
7 Correct 128 ms 10020 KB Output is correct
8 Correct 129 ms 9896 KB Output is correct
9 Correct 79 ms 6428 KB Output is correct
10 Correct 123 ms 9824 KB Output is correct
11 Correct 128 ms 9824 KB Output is correct
12 Correct 84 ms 6368 KB Output is correct
13 Correct 83 ms 6672 KB Output is correct
14 Correct 87 ms 6772 KB Output is correct
15 Correct 90 ms 6904 KB Output is correct
16 Correct 3 ms 460 KB Output is correct
17 Correct 78 ms 6496 KB Output is correct
18 Correct 79 ms 6444 KB Output is correct
19 Correct 84 ms 6364 KB Output is correct
20 Correct 121 ms 9824 KB Output is correct
21 Correct 133 ms 9836 KB Output is correct
22 Correct 133 ms 9764 KB Output is correct