oj.uz

Submission #130657

# Submission time Handle Problem Language Result Execution time Memory
130657 2019-07-15T19:15:59 Z sealnot123 Mechanical Doll (IOI18_doll) C++14
28 / 100
 118 ms 11816 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");
    for(i=0;i<m;i++){
        sorted.pb(BIT[lgn][i]);
    }
    sort(all(sorted));
    for(i=0;i<m;i++){
        int t = lower_bound(all(sorted), BIT[lgn][i])-sorted.begin();
        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
*/

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

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 244 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 244 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 244 KB wrong motion
2 Halted 0 ms 0 KB -

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 2 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 73 ms 8740 KB Output is correct
3 Correct 80 ms 8700 KB Output is correct
4 Correct 116 ms 11104 KB Output is correct

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 73 ms 8740 KB Output is correct
3 Correct 80 ms 8700 KB Output is correct
4 Correct 116 ms 11104 KB Output is correct
5 Incorrect 118 ms 11816 KB wrong motion
6 Halted 0 ms 0 KB -