oj.uz

Submission #132703

# Submission time Handle Problem Language Result Execution time Memory
132703 2019-07-19T11:16:29 Z dvdg6566 Mechanical Doll (IOI18_doll) C++14
85.553 / 100
 694 ms 14476 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[130100];
int c=-1;
vi X,Y;

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

void f2(int sizes, int numf2, int exit, int rt){
  // cout<<sizes<<' '<<numf2<<' '<<exit<<'\n';
  if (sizes == numf2){
    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);
    f2 (sizes/2,numf2/2,0,rt);
    Y[t] = c--;
    if (exit)f2 (sizes/2,numf2/2,1,rt);
    else f2(sizes/2,numf2/2,0,rt);
    return;
  }
  if (numf2 == 2){
    if (sizes == 1){
      X.pb(rt);
      Y.pb(1-exit);
    }else{
      X.pb(1);
      Y.pb(1-exit);
    }
    return;
  }
  if (sizes*2 <= numf2){
    X.pb(rt);
    Y.pb(c--);
    f2 (sizes, numf2/2, 0, rt);
    return;
  }else{
    int t=SZ(X);
    X.pb(c--);
    Y.pb(0);
    f2 (sizes-numf2/2, numf2/2, 0, rt);
    Y[t] = c--;
    f2 (numf2/2,numf2/2,exit,rt);
    return;
  }
}

vi C;
int states[270100];

void simulate(int x){
  map<int,int> states;
  for (int t=0;t<SZ(occ[x]);++t){
    int cur=C[x];
    // cout<<"Simulate with dest "<<occ[x][t]<< " from "<<cur<<'\n';
    while (1){
      int nxt = X[-1-cur];
      if (states[-1-cur] == 1){
        nxt = Y[-1-cur];
      }
      // cout<<"At "<<cur<<" aka "<<-1-cur<<" next is "<<nxt<<'\n';
      if (nxt == 1){
        // cout<<"Change "<<-1-cur<<" when the state is "<<cur<<'\n';
        if (states[-1-cur] == 1){
          Y[-1-cur] = occ[x][t];
        }else{
          X[-1-cur] = occ[x][t];
        }
        states[-1-cur] = 1-states[-1-cur];
        break;
      }else{
        states[-1-cur] = 1-states[-1-cur];
        cur = nxt;
      }
    }
  }
}

void create_circuit(int M, std::vector<int> A) {
  int N = A.size();
  C.resize(M+1,-1);
  if (M == 1){
    int t = MSB(N-1);
    int l = (1<<t);
    C[1] = c--; 
    C[0]=1;
    f2(N,l,1,-1);
    answer(C,X,Y);
    return;
  }
  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]);
    }else{
      int N = SZ(occ[i]);
      int t = MSB(N-1);
      int l = (1<<t);
      int cc=c;
      C[i] = c--;
      fill(N,l,cc);
    }
    // cout<<"Value "<<i<<" ends at "<<c<<'\n';
    // for (int i=0;i<SZ(X);++i)cout<<X[i]<<' '<<Y[i]<<'\n';
  }
  // for (int i=0;i<=M;++i)cout<<C[i]<<' ';cout<<"\n\n";
  // for (int i=0;i<SZ(X);++i)cout<<X[i]<<' '<<Y[i]<<'\n';
  for (int i=0;i<=M;++i){
    if (SZ(occ[i]) > 4)simulate(i);
  }
  // for (int i=0;i<=M;++i)cout<<C[i]<<' ';cout<<"\n\n";
  // for (int i=0;i<SZ(X);++i)cout<<X[i]<<' '<<Y[i]<<'\n';
  // 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 3276 KB Output is correct
2 Correct 33 ms 7072 KB Output is correct
3 Correct 25 ms 6604 KB Output is correct
4 Correct 3 ms 3276 KB Output is correct
5 Correct 13 ms 4428 KB Output is correct
6 Correct 47 ms 8352 KB Output is correct
7 Correct 3 ms 3276 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3276 KB Output is correct
2 Correct 33 ms 7072 KB Output is correct
3 Correct 25 ms 6604 KB Output is correct
4 Correct 3 ms 3276 KB Output is correct
5 Correct 13 ms 4428 KB Output is correct
6 Correct 47 ms 8352 KB Output is correct
7 Correct 3 ms 3276 KB Output is correct
8 Correct 56 ms 8844 KB Output is correct
9 Correct 66 ms 9336 KB Output is correct
10 Correct 82 ms 11704 KB Output is correct
11 Correct 3 ms 3276 KB Output is correct
12 Correct 3 ms 3276 KB Output is correct
13 Correct 4 ms 3276 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3276 KB Output is correct
2 Correct 33 ms 7072 KB Output is correct
3 Correct 25 ms 6604 KB Output is correct
4 Correct 3 ms 3276 KB Output is correct
5 Correct 13 ms 4428 KB Output is correct
6 Correct 47 ms 8352 KB Output is correct
7 Correct 3 ms 3276 KB Output is correct
8 Correct 56 ms 8844 KB Output is correct
9 Correct 66 ms 9336 KB Output is correct
10 Correct 82 ms 11704 KB Output is correct
11 Correct 3 ms 3276 KB Output is correct
12 Correct 3 ms 3276 KB Output is correct
13 Correct 4 ms 3276 KB Output is correct
14 Correct 104 ms 13308 KB Output is correct
15 Correct 73 ms 8256 KB Output is correct
16 Correct 90 ms 10892 KB Output is correct
17 Correct 3 ms 3276 KB Output is correct
18 Correct 3 ms 3276 KB Output is correct
19 Correct 3 ms 3296 KB Output is correct
20 Correct 99 ms 12416 KB Output is correct
21 Correct 5 ms 3276 KB Output is correct
22 Correct 3 ms 3276 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3276 KB Output is correct
2 Correct 47 ms 7616 KB Output is correct
3 Correct 48 ms 8044 KB Output is correct
4 Correct 74 ms 9756 KB Output is correct

Subtask #6
41.5530038336 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3276 KB Output is correct
2 Correct 47 ms 7616 KB Output is correct
3 Correct 48 ms 8044 KB Output is correct
4 Correct 74 ms 9756 KB Output is correct
5 Partially correct 131 ms 14116 KB Output is partially correct
6 Partially correct 136 ms 13724 KB Output is partially correct
7 Partially correct 149 ms 13848 KB Output is partially correct
8 Partially correct 151 ms 13000 KB Output is partially correct
9 Partially correct 657 ms 9648 KB Output is partially correct
10 Partially correct 694 ms 14476 KB Output is partially correct
11 Partially correct 312 ms 11724 KB Output is partially correct
12 Partially correct 195 ms 8836 KB Output is partially correct
13 Partially correct 91 ms 10052 KB Output is partially correct
14 Partially correct 86 ms 10200 KB Output is partially correct
15 Partially correct 93 ms 10300 KB Output is partially correct
16 Partially correct 7 ms 3532 KB Output is partially correct
17 Partially correct 151 ms 8552 KB Output is partially correct
18 Partially correct 236 ms 9288 KB Output is partially correct
19 Partially correct 199 ms 8592 KB Output is partially correct
20 Partially correct 183 ms 11256 KB Output is partially correct
21 Partially correct 342 ms 11316 KB Output is partially correct
22 Partially correct 265 ms 11012 KB Output is partially correct