oj.uz

Submission #198067

# Submission time Handle Problem Language Result Execution time Memory
198067 2020-01-24T15:14:47 Z DavidDamian Mechanical Doll (IOI18_doll) C++11
53 / 100
 148 ms 20116 KB 
#include "doll.h"
using namespace std;
#define debug(x) cerr<<#x<<" = "<<x<<endl
vector<int> destino[100006];
int X[4000006];
int Y[4000006];
int create_tree(int i,int limit,int lv,int sum,int n,int root,int trigger)
{
    int last=i;
    if(lv==limit-1){
        int threshold=(1<<limit)-n;
        if(sum<threshold)
            X[(i+root-1)-1]=-root;
        else
            X[(i+root-1)-1]=destino[trigger][sum-threshold];
        sum+=(1<<lv);
        //debug(sum);
        if(sum<threshold)
            Y[(i+root-1)-1]=-root;
        else
            Y[(i+root-1)-1]=destino[trigger][sum-threshold];
    }
    else{
        X[i+root-1-1]=-(2*i+root-1);
        last=max(last,create_tree(i*2,limit,lv+1,sum,n,root,trigger));
        Y[i+root-1-1]=-(2*i+root);
        last=max(last,create_tree(i*2+1,limit,lv+1,sum+(1<<lv),n,root,trigger));
    }
    return last;
}
int log_n[400005];
int k;
void create_circuit(int m, vector<int> A) {
  int n=A.size();
  log_n[2]=1;
  for(int i=3;i<=400000;i++){
    log_n[i]=log_n[(i+1)/2]+1;
  }
  vector<int> C(m + 1);
  C[0]=A[0];
  for(int i=0;i<n-1;i++){
    destino[ A[i] ].push_back(A[i+1]);
  }
  destino[ A[n-1] ].push_back(0);
  for(int i=1;i<=m;i++){
    if(destino[i].size()==0) C[i]=0;
    else if(destino[i].size()==1) C[i]=destino[i][0];
    else{
        int limit=log_n[ destino[i].size() ];
        C[i]=-(k+1);
        k+=create_tree(1,limit,0,0,destino[i].size(),k+1,i);
        //debug(k);
    }
  }
  vector<int> x,y;
  for(int i=0;i<k;i++){
    x.push_back(X[i]);
    y.push_back(Y[i]);
  }
  answer(C, x, y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4172 KB Output is correct
2 Correct 39 ms 7884 KB Output is correct
3 Correct 31 ms 7508 KB Output is correct
4 Correct 4 ms 4172 KB Output is correct
5 Correct 16 ms 5308 KB Output is correct
6 Correct 51 ms 9292 KB Output is correct
7 Correct 4 ms 4172 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4172 KB Output is correct
2 Correct 39 ms 7884 KB Output is correct
3 Correct 31 ms 7508 KB Output is correct
4 Correct 4 ms 4172 KB Output is correct
5 Correct 16 ms 5308 KB Output is correct
6 Correct 51 ms 9292 KB Output is correct
7 Correct 4 ms 4172 KB Output is correct
8 Correct 68 ms 10056 KB Output is correct
9 Correct 78 ms 10480 KB Output is correct
10 Correct 108 ms 13392 KB Output is correct
11 Correct 4 ms 4172 KB Output is correct
12 Correct 4 ms 4172 KB Output is correct
13 Correct 3 ms 4216 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4172 KB Output is correct
2 Correct 39 ms 7884 KB Output is correct
3 Correct 31 ms 7508 KB Output is correct
4 Correct 4 ms 4172 KB Output is correct
5 Correct 16 ms 5308 KB Output is correct
6 Correct 51 ms 9292 KB Output is correct
7 Correct 4 ms 4172 KB Output is correct
8 Correct 68 ms 10056 KB Output is correct
9 Correct 78 ms 10480 KB Output is correct
10 Correct 108 ms 13392 KB Output is correct
11 Correct 4 ms 4172 KB Output is correct
12 Correct 4 ms 4172 KB Output is correct
13 Correct 3 ms 4216 KB Output is correct
14 Correct 125 ms 14920 KB Output is correct
15 Correct 59 ms 9732 KB Output is correct
16 Correct 102 ms 12616 KB Output is correct
17 Correct 3 ms 4172 KB Output is correct
18 Correct 4 ms 4172 KB Output is correct
19 Correct 4 ms 4172 KB Output is correct
20 Correct 110 ms 13884 KB Output is correct
21 Correct 3 ms 4172 KB Output is correct
22 Correct 4 ms 4172 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 4172 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 4172 KB Output is partially correct
2 Correct 70 ms 10184 KB Output is correct
3 Partially correct 90 ms 14052 KB Output is partially correct
4 Partially correct 114 ms 14844 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 4172 KB Output is partially correct
2 Correct 70 ms 10184 KB Output is correct
3 Partially correct 90 ms 14052 KB Output is partially correct
4 Partially correct 114 ms 14844 KB Output is partially correct
5 Partially correct 148 ms 17220 KB Output is partially correct
6 Partially correct 143 ms 18544 KB Output is partially correct
7 Partially correct 130 ms 18064 KB Output is partially correct
8 Partially correct 145 ms 19264 KB Output is partially correct
9 Partially correct 87 ms 14840 KB Output is partially correct
10 Partially correct 129 ms 19664 KB Output is partially correct
11 Partially correct 129 ms 20116 KB Output is partially correct
12 Partially correct 93 ms 14720 KB Output is partially correct
13 Partially correct 85 ms 13628 KB Output is partially correct
14 Partially correct 94 ms 13244 KB Output is partially correct
15 Partially correct 98 ms 12732 KB Output is partially correct
16 Partially correct 6 ms 4428 KB Output is partially correct
17 Partially correct 73 ms 12600 KB Output is partially correct
18 Partially correct 72 ms 12728 KB Output is partially correct
19 Partially correct 80 ms 13152 KB Output is partially correct
20 Partially correct 105 ms 15588 KB Output is partially correct
21 Partially correct 115 ms 18112 KB Output is partially correct
22 Partially correct 109 ms 15048 KB Output is partially correct