oj.uz

Submission #198390

# Submission time Handle Problem Language Result Execution time Memory
198390 2020-01-25T18:37:17 Z DavidDamian Mechanical Doll (IOI18_doll) C++11
100 / 100
 233 ms 18492 KB 
#include "doll.h"
#include<bits/stdc++.h>
using namespace std;
///Binary Tree
///Create a tree of switches that produces a sequence of nodes
#define debug(x) cerr<<#x<<" = "<<x<<endl
struct parent
{
    int p;
    short edge;
};
vector<int> X;
vector<int> Y;
map<int,parent> memo;
int NEXT_FREE_INDEX=1;
int limit;
void createTree(int i,int lv,int sum,int unused) ///Creates a tree of switches to branch exits
{
    if(lv==limit-1){ //Last level of switches, so we direct the switches to the number of the sum
        if(unused==1) //We have to kill that edge
            X.push_back(-1);
        else{
            X.push_back(sum);
            parent x={i,0};
            memo[sum]=x; //We store where it is that number in the tree
        }
        sum+=(1<<lv);
        parent x={i,1};
        Y.push_back(sum);
        memo[sum]=x;
    }
    else{
        int child_size=(1<<(limit-lv-1));
        if(unused>=child_size){ //Drop left child because it not useful
            X.push_back(-1);
            Y.push_back(-NEXT_FREE_INDEX);
            NEXT_FREE_INDEX++;
            createTree(NEXT_FREE_INDEX-1,lv+1,sum+(1<<lv),unused-child_size); //And just create right child
        }
        else{ //Create both children
            X.push_back(-NEXT_FREE_INDEX);
            NEXT_FREE_INDEX++;
            Y.push_back(0);
            createTree(NEXT_FREE_INDEX-1,lv+1,sum,unused);
            Y[i-1]=-NEXT_FREE_INDEX;
            NEXT_FREE_INDEX++;
            createTree(NEXT_FREE_INDEX-1,lv+1,sum+(1<<lv),0);
        }
    }
}
void create_circuit(int m, vector<int> A) {

  A.push_back(0);
  int n=A.size();
  vector<int> C(m+1);
  for(int i=0;i<=m;i++){ //We direct all the triggers to a single root
    C[i]=-1;
  }
  int LOG=0;
  while((1<<LOG)<n){
    LOG++;
  }
  NEXT_FREE_INDEX++;
  limit=LOG;
  createTree(1,0,0,(1<<LOG)-n);
  int j=0;
  map<int,parent>::iterator it;
    for(it=memo.begin();it!=memo.end();it++){
        pair<int,parent> x=(*it);
        int p=x.second.p;
        int edge=x.second.edge;
        if(edge==0) X[p-1]=A[j]; //Attach the correct node to exit 0 of the switch p-1
        else Y[p-1]=A[j]; //Attach the correct node to exit 1 of the switch p-1
        j++;
    }
    memo.clear();
  answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 54 ms 6408 KB Output is correct
3 Correct 51 ms 6524 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 1356 KB Output is correct
6 Correct 105 ms 9672 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 54 ms 6408 KB Output is correct
3 Correct 51 ms 6524 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 1356 KB Output is correct
6 Correct 105 ms 9672 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 111 ms 12256 KB Output is correct
9 Correct 144 ms 12564 KB Output is correct
10 Correct 227 ms 18468 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 2 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 54 ms 6408 KB Output is correct
3 Correct 51 ms 6524 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 1356 KB Output is correct
6 Correct 105 ms 9672 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 111 ms 12256 KB Output is correct
9 Correct 144 ms 12564 KB Output is correct
10 Correct 227 ms 18468 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 2 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 214 ms 18232 KB Output is correct
15 Correct 143 ms 12012 KB Output is correct
16 Correct 187 ms 18056 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 190 ms 18492 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

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 1 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 1 ms 204 KB Output is correct
2 Correct 109 ms 11588 KB Output is correct
3 Correct 138 ms 11480 KB Output is correct
4 Correct 222 ms 16968 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 109 ms 11588 KB Output is correct
3 Correct 138 ms 11480 KB Output is correct
4 Correct 222 ms 16968 KB Output is correct
5 Correct 233 ms 18084 KB Output is correct
6 Correct 221 ms 17816 KB Output is correct
7 Correct 215 ms 18088 KB Output is correct
8 Correct 194 ms 17712 KB Output is correct
9 Correct 137 ms 11548 KB Output is correct
10 Correct 221 ms 17596 KB Output is correct
11 Correct 222 ms 17328 KB Output is correct
12 Correct 146 ms 11592 KB Output is correct
13 Correct 118 ms 11800 KB Output is correct
14 Correct 115 ms 12004 KB Output is correct
15 Correct 132 ms 11980 KB Output is correct
16 Correct 3 ms 588 KB Output is correct
17 Correct 112 ms 11412 KB Output is correct
18 Correct 137 ms 11560 KB Output is correct
19 Correct 139 ms 11584 KB Output is correct
20 Correct 230 ms 17576 KB Output is correct
21 Correct 191 ms 17296 KB Output is correct
22 Correct 213 ms 17348 KB Output is correct