Submission #130791

#	Time	Username	Problem	Language	Result	Execution time	Memory
130791		sealnot123	Mechanical Doll (IOI18_doll)	C++14	100 / 100	144 ms	12768 KiB

doll

#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 (stderr)

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 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 18 / 18
• Subtask 6: 56 / 56