oj.uz

Submission #132685

# Submission time Handle Problem Language Result Execution time Memory
132685 2019-07-19T10:36:58 Z dvdg6566 Mechanical Doll (IOI18_doll) C++14
34 / 100
 127 ms 12320 KB 
#include "doll.h"
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
#define pb emplace_back
#define SZ(x) (int)x.size()
 
inline int MSB(unsigned int x){
  return 32-__builtin_clz(x);
}
#define INF 1e9

vi occ[100100];
int c=-1;
vi X,Y;

void fill(int sizes, int numfill, int exit, int rt){
  // cout<<sizes<<' '<<numfill<<' '<<exit<<'\n';
  if (sizes == numfill){
    if (sizes == 2){
      if (exit){
        X.pb(1);
        Y.pb(0);
      }else{
        X.pb(1);
        Y.pb(1);
      }
      return;
    }
    int t=SZ(X);
    X.pb(c--);
    Y.pb(0);
    fill (sizes/2,numfill/2,0,rt);
    Y[t] = c--;
    if (exit)fill (sizes/2,numfill/2,1,rt);
    else fill(sizes/2,numfill/2,0,rt);
    return;
  }
  if (numfill == 2){
    if (sizes == 1){
      X.pb(rt);
      Y.pb(1-exit);
    }else{
      X.pb(1);
      Y.pb(1-exit);
    }
    return;
  }
  if (sizes*2 <= numfill){
    X.pb(rt);
    Y.pb(c--);
    fill (sizes, numfill/2, 0, rt);
    return;
  }else{
    int t=SZ(X);
    X.pb(c--);
    Y.pb(0);
    fill (sizes-numfill/2, numfill/2, 0, rt);
    Y[t] = c--;
    fill (numfill/2,numfill/2,exit,rt);
    return;
  }
}

void create_circuit(int M, std::vector<int> A) {
  int N = A.size();
  std::vector<int> C(M + 1,-1);
  if (M == 1){
    int t = MSB(N-1);
    int l = (1<<t);
    C[1] = c--; 
    C[0]=1;
    fill(N,l,1,-1);
    



  }else{
    occ[0].pb(A[0]);
    for (int i=0;i<N-1;++i){
      occ[A[i]].pb(A[i+1]);
    }
    occ[A[N-1]].pb(0);
    for (int i=0;i<=M;++i){
      if (SZ(occ[i]) == 0){
        C[i]=0;
      }else if(SZ(occ[i]) == 1){
        C[i]=occ[i][0];
      }else if (SZ(occ[i]) == 2){
        C[i] = c;
        --c;
        X.pb(occ[i][0]);
        Y.pb(occ[i][1]);
      }else if (SZ(occ[i]) == 3){
        int a = c;
        C[i] = a;
        c -= 3;
        X.pb(a-1);
        Y.pb(a-2);
        X.pb(occ[i][0]);
        Y.pb(a);
        X.pb(occ[i][1]);
        Y.pb(occ[i][2]);
      }else if (SZ(occ[i]) == 4){
        int a = c;
        C[i] = a;
        c -= 3;
        X.pb(a-1);
        Y.pb(a-2);
        X.pb(occ[i][0]);
        Y.pb(occ[i][2]);
        X.pb(occ[i][1]);
        Y.pb(occ[i][3]);
      }
    }
  }
  // for (int i=0;i<=M;++i)cout<<C[i]<<' ';cout<<'\n';
  answer(C,X,Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 43 ms 6340 KB Output is correct
3 Correct 28 ms 5964 KB Output is correct
4 Correct 3 ms 2636 KB Output is correct
5 Correct 18 ms 3788 KB Output is correct
6 Correct 54 ms 7644 KB Output is correct
7 Correct 3 ms 2636 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 43 ms 6340 KB Output is correct
3 Correct 28 ms 5964 KB Output is correct
4 Correct 3 ms 2636 KB Output is correct
5 Correct 18 ms 3788 KB Output is correct
6 Correct 54 ms 7644 KB Output is correct
7 Correct 3 ms 2636 KB Output is correct
8 Correct 56 ms 8028 KB Output is correct
9 Correct 68 ms 8632 KB Output is correct
10 Correct 94 ms 10956 KB Output is correct
11 Correct 3 ms 2636 KB Output is correct
12 Correct 3 ms 2636 KB Output is correct
13 Correct 3 ms 2636 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 43 ms 6340 KB Output is correct
3 Correct 28 ms 5964 KB Output is correct
4 Correct 3 ms 2636 KB Output is correct
5 Correct 18 ms 3788 KB Output is correct
6 Correct 54 ms 7644 KB Output is correct
7 Correct 3 ms 2636 KB Output is correct
8 Correct 56 ms 8028 KB Output is correct
9 Correct 68 ms 8632 KB Output is correct
10 Correct 94 ms 10956 KB Output is correct
11 Correct 3 ms 2636 KB Output is correct
12 Correct 3 ms 2636 KB Output is correct
13 Correct 3 ms 2636 KB Output is correct
14 Correct 127 ms 12320 KB Output is correct
15 Correct 53 ms 7408 KB Output is correct
16 Correct 80 ms 9872 KB Output is correct
17 Correct 3 ms 2636 KB Output is correct
18 Correct 3 ms 2636 KB Output is correct
19 Correct 3 ms 2636 KB Output is correct
20 Correct 92 ms 11264 KB Output is correct
21 Correct 3 ms 2636 KB Output is correct
22 Correct 3 ms 2636 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2636 KB wrong serial number
2 Halted 0 ms 0 KB -

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 63 ms 6868 KB Output is correct
3 Correct 55 ms 7432 KB Output is correct
4 Correct 83 ms 9120 KB Output is correct

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 63 ms 6868 KB Output is correct
3 Correct 55 ms 7432 KB Output is correct
4 Correct 83 ms 9120 KB Output is correct
5 Incorrect 50 ms 6852 KB wrong serial number
6 Halted 0 ms 0 KB -