oj.uz

Submission #130791

# Submission time Handle Problem Language Result Execution time Memory
130791 2019-07-16T05:30:27 Z sealnot123 Mechanical Doll (IOI18_doll) C++14
100 / 100
 144 ms 12768 KB 
#ifdef LOCAL
#include "grader.cpp"
#endif

#include "doll.h"
#include<bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
#define SZ(a) (int)(a).size()
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PLL;
typedef pair<int,int> PII;
typedef double D;
typedef long double LD;
typedef vector<int> VI;
const int N = 100005, M = 200005;
int sw, m, lgn = -1;
vector<int> BIT[22], X, Y, C, ORDER;
vector<int> sorted, arrange;
int build(int l, int r){
    if(l == r) return arrange[l];
    int nw = ++sw;
    X.pb(0); Y.pb(0);
    int mid = (l+r)>>1;
    int a,b;
    a = build(l, mid);
    b = build(mid+1, r);
    X[nw-1] = a;
    Y[nw-1] = b;
    return -nw;
}
int circuit(int bit, int built){
    if(bit == 0) return 0;
    int nw = ++sw, a, b;
    X.pb(-1); Y.pb(-1);
    if((1<<(bit-1))&m) a = build(built, built+(1<<(bit-1))-1), built += (1<<(bit-1));
    else a = -1;
    b = circuit(bit-1, built);
    X[nw-1] = a; Y[nw-1] = b;
//    printf("%d : %d %d %d\n",bit,nw,X[nw-1],Y[nw-1]);
    return -nw;
}
void create_circuit(int nn, VI order) {
    int i,j,k,l,a,b,c,d;
    ORDER = order;
    m = SZ(order);
    BIT[0].pb(0);
    for(i=1;i<19;i++){
        BIT[i].assign(1<<i, 0);
        for(j=0;j<(1<<i);j++){
            assert((j&((1<<(i-1))-1)) < SZ(BIT[i-1]));
            BIT[i][j] = (BIT[i-1][j&((1<<(i-1))-1)]<<1)|(j>=(1<<(i-1)));
        }
        if(lgn == -1 && (1<<i)>m){
            lgn = i;
            break;
        }
    }
//    printf("lgn = %d\n",lgn);
//    for(int it : BIT[lgn]) printf("%d ",it);
//    printf("\n");
    int last = 0;
    for(i=lgn;i>0;i--){
        if(m&(1<<(i-1))){
//            printf("%d :: ",i-1);
            for(j = last; j < last+(1<<(i-1)); j++) sorted.pb(BIT[lgn][j]);
//            printf("\n");
        }
        last += 1<<(i-1);
    }
    sort(all(sorted));
    for(i=0;i<(1<<lgn);i++){
        int t = lower_bound(all(sorted), BIT[lgn][i])-sorted.begin();
        if(t<SZ(sorted) && sorted[t] == BIT[lgn][i]) arrange.pb(order[t]);
    }
//    printf("sorted: ");
//    for(int it : sorted) printf("%d ",it);
//    printf("\n");
//    printf("arrange: ");
//    for(int it : arrange) printf("%d ",it);
//    printf("\n");
    circuit(lgn, 0);
    C.assign(nn+1, -1);
    answer(C, X, Y);
}
/*
4 4
1 2 1 3

5 5
1 2 3 4 5
*/

Compilation message

doll.cpp: In function 'void create_circuit(int, VI)':
doll.cpp:46:13: warning: unused variable 'k' [-Wunused-variable]
   46 |     int i,j,k,l,a,b,c,d;
      |             ^
doll.cpp:46:15: warning: unused variable 'l' [-Wunused-variable]
   46 |     int i,j,k,l,a,b,c,d;
      |               ^
doll.cpp:46:17: warning: unused variable 'a' [-Wunused-variable]
   46 |     int i,j,k,l,a,b,c,d;
      |                 ^
doll.cpp:46:19: warning: unused variable 'b' [-Wunused-variable]
   46 |     int i,j,k,l,a,b,c,d;
      |                   ^
doll.cpp:46:21: warning: unused variable 'c' [-Wunused-variable]
   46 |     int i,j,k,l,a,b,c,d;
      |                     ^
doll.cpp:46:23: warning: unused variable 'd' [-Wunused-variable]
   46 |     int i,j,k,l,a,b,c,d;
      |                       ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 78 ms 5728 KB Output is correct
3 Correct 67 ms 5956 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 1356 KB Output is correct
6 Correct 69 ms 6900 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 78 ms 5728 KB Output is correct
3 Correct 67 ms 5956 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 1356 KB Output is correct
6 Correct 69 ms 6900 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 93 ms 10056 KB Output is correct
9 Correct 101 ms 10636 KB Output is correct
10 Correct 142 ms 12768 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 78 ms 5728 KB Output is correct
3 Correct 67 ms 5956 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 1356 KB Output is correct
6 Correct 69 ms 6900 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 93 ms 10056 KB Output is correct
9 Correct 101 ms 10636 KB Output is correct
10 Correct 142 ms 12768 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 138 ms 12184 KB Output is correct
15 Correct 96 ms 9704 KB Output is correct
16 Correct 124 ms 12012 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 2 ms 204 KB Output is correct
20 Correct 131 ms 12456 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 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 1 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 232 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 90 ms 8660 KB Output is correct
3 Correct 98 ms 8680 KB Output is correct
4 Correct 123 ms 11052 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 90 ms 8660 KB Output is correct
3 Correct 98 ms 8680 KB Output is correct
4 Correct 123 ms 11052 KB Output is correct
5 Correct 144 ms 11752 KB Output is correct
6 Correct 132 ms 11492 KB Output is correct
7 Correct 127 ms 11628 KB Output is correct
8 Correct 139 ms 11320 KB Output is correct
9 Correct 87 ms 8708 KB Output is correct
10 Correct 128 ms 11276 KB Output is correct
11 Correct 134 ms 11108 KB Output is correct
12 Correct 94 ms 8888 KB Output is correct
13 Correct 92 ms 9240 KB Output is correct
14 Correct 92 ms 9424 KB Output is correct
15 Correct 93 ms 9448 KB Output is correct
16 Correct 4 ms 588 KB Output is correct
17 Correct 74 ms 7232 KB Output is correct
18 Correct 87 ms 8896 KB Output is correct
19 Correct 96 ms 8892 KB Output is correct
20 Correct 120 ms 11116 KB Output is correct
21 Correct 126 ms 11108 KB Output is correct
22 Correct 124 ms 11112 KB Output is correct