oj.uz

Submission #464032

# Submission time Handle Problem Language Result Execution time Memory
464032 2021-08-12T09:35:03 Z oscar1f Mechanical Doll (IOI18_doll) C++17
100 / 100
 144 ms 20404 KB 
#include<bits/stdc++.h>
#include "doll.h"
using namespace std;

const int DECA=(1<<18),INFINI=1000*1000*1000;
int nbDec,longChaine,date,decalage;
vector<int> chaine,direc,prem,deuz;
int arbreBin[2*DECA],tour[2*DECA][3];

void chute(int pos,int id) {
  if (pos<decalage) {
    tour[pos][2]=1-tour[pos][2];
    chute(tour[pos][1-tour[pos][2]],id);
  }
  else {
    arbreBin[pos]=chaine[id];
  }
}

void create_circuit(int M,vector<int> A) {
  nbDec=M;
  A.push_back(0);
  longChaine=A.size();
  chaine=A;
  decalage=1;
  while (decalage<longChaine) {
    decalage*=2;
  }
  for (int i=1;i<2*DECA;i++) {
    arbreBin[i]=INFINI;
    tour[i][0]=1;
    tour[i][1]=1;
  }
  for (int i=decalage-1;i>=decalage-longChaine;i--) {
    arbreBin[decalage+i]=1;
  }
  for (int i=0;i<=nbDec;i++) {
    direc.push_back(-1);
  }
  
  for (int i=decalage-1;i>0;i--) {
    if (arbreBin[2*i]!=INFINI) {
      tour[i][0]=2*i;
      arbreBin[i]=INFINI+1;
    }
    if (arbreBin[2*i+1]!=INFINI) {
      tour[i][1]=2*i+1;
      arbreBin[i]=INFINI+1;
    }
  }

  /*cout<<decalage<<endl;
  for (int i=1;i<decalage;i++) {
    cout<<tour[i][0]<<" "<<tour[i][1]<<endl;
  }*/
  
  for (int i=0;i<longChaine;i++) {
    chute(1,i);
  }  
  date=-1;

  for (int i=1;i<2*decalage;i++) {
    if (arbreBin[i]==INFINI+1) {
      arbreBin[i]=date;
      date--;
    }
    else if (arbreBin[i]==INFINI) {
      arbreBin[i]=-1;
    }
  }
  for (int i=1;i<decalage;i++) {
    if (arbreBin[i]<-1 or i==1) {
      prem.push_back(arbreBin[tour[i][0]]);
      deuz.push_back(arbreBin[tour[i][1]]);
    }
  }
  /*for (int i=0;i<direc.size();i++) {
    cout<<direc[i]<<" ";
  }
  cout<<endl;
  for (int i=0;i<prem.size();i++) {
    cout<<prem[i]<<" "<<deuz[i]<<endl;
  }*/
  answer(direc,prem,deuz);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8396 KB Output is correct
2 Correct 56 ms 13176 KB Output is correct
3 Correct 48 ms 13040 KB Output is correct
4 Correct 5 ms 8396 KB Output is correct
5 Correct 16 ms 9796 KB Output is correct
6 Correct 73 ms 15244 KB Output is correct
7 Correct 5 ms 8396 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8396 KB Output is correct
2 Correct 56 ms 13176 KB Output is correct
3 Correct 48 ms 13040 KB Output is correct
4 Correct 5 ms 8396 KB Output is correct
5 Correct 16 ms 9796 KB Output is correct
6 Correct 73 ms 15244 KB Output is correct
7 Correct 5 ms 8396 KB Output is correct
8 Correct 96 ms 16468 KB Output is correct
9 Correct 92 ms 16804 KB Output is correct
10 Correct 134 ms 20404 KB Output is correct
11 Correct 5 ms 8396 KB Output is correct
12 Correct 5 ms 8468 KB Output is correct
13 Correct 5 ms 8396 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8396 KB Output is correct
2 Correct 56 ms 13176 KB Output is correct
3 Correct 48 ms 13040 KB Output is correct
4 Correct 5 ms 8396 KB Output is correct
5 Correct 16 ms 9796 KB Output is correct
6 Correct 73 ms 15244 KB Output is correct
7 Correct 5 ms 8396 KB Output is correct
8 Correct 96 ms 16468 KB Output is correct
9 Correct 92 ms 16804 KB Output is correct
10 Correct 134 ms 20404 KB Output is correct
11 Correct 5 ms 8396 KB Output is correct
12 Correct 5 ms 8468 KB Output is correct
13 Correct 5 ms 8396 KB Output is correct
14 Correct 127 ms 20104 KB Output is correct
15 Correct 85 ms 16316 KB Output is correct
16 Correct 127 ms 19856 KB Output is correct
17 Correct 5 ms 8396 KB Output is correct
18 Correct 5 ms 8396 KB Output is correct
19 Correct 5 ms 8396 KB Output is correct
20 Correct 131 ms 20228 KB Output is correct
21 Correct 5 ms 8396 KB Output is correct
22 Correct 5 ms 8500 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8396 KB Output is correct
2 Correct 80 ms 13776 KB Output is correct
3 Correct 90 ms 13728 KB Output is correct
4 Correct 118 ms 16580 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8396 KB Output is correct
2 Correct 80 ms 13776 KB Output is correct
3 Correct 90 ms 13728 KB Output is correct
4 Correct 118 ms 16580 KB Output is correct
5 Correct 127 ms 18284 KB Output is correct
6 Correct 124 ms 17668 KB Output is correct
7 Correct 123 ms 17732 KB Output is correct
8 Correct 144 ms 17700 KB Output is correct
9 Correct 81 ms 13804 KB Output is correct
10 Correct 121 ms 17312 KB Output is correct
11 Correct 119 ms 17028 KB Output is correct
12 Correct 83 ms 14048 KB Output is correct
13 Correct 97 ms 14896 KB Output is correct
14 Correct 85 ms 14588 KB Output is correct
15 Correct 85 ms 14648 KB Output is correct
16 Correct 7 ms 8652 KB Output is correct
17 Correct 80 ms 14364 KB Output is correct
18 Correct 85 ms 14052 KB Output is correct
19 Correct 79 ms 14052 KB Output is correct
20 Correct 126 ms 17448 KB Output is correct
21 Correct 121 ms 16932 KB Output is correct
22 Correct 128 ms 16980 KB Output is correct