oj.uz

Submission #198148

# Submission time Handle Problem Language Result Execution time Memory
198148 2020-01-24T20:53:02 Z DavidDamian Mechanical Doll (IOI18_doll) C++11
12 / 100
 1000 ms 12480 KB 
#include "doll.h"
#include<bits/stdc++.h>
using namespace std;
#define debug(x) cerr<<#x<<" = "<<x<<endl
vector<int> destino[100006];
int X[400006];
int Y[400006];
int moved[400006];
int parent[100005];
int removed[100005];
void connectLeaves(int n,int trigger)
{
    int leaf=0;
    for(int i=0;i<n;i++){
        if(removed[i]) continue;
        int id=parent[i];
        if(X[id]==i && !moved[id]) {
            X[id]=destino[trigger][leaf];
            moved[id]=1;
        }
        else Y[id]=destino[trigger][leaf];
        leaf++;
    }
}
void explore_PhantomTree(int limit,int lv,int sum)
{
    if(lv==limit-1){
        removed[sum]=1;
        sum+=(1<<lv);
        removed[sum]=1;
    }
    else{
        explore_PhantomTree(limit,lv+1,sum);
        explore_PhantomTree(limit,lv+1,sum+(1<<lv));
    }
}
int k;
int NEXT_FREE_INDEX=0;
void createTree(int i,int limit,int lv,int sum,int notDesired)
{
    //debug(i);
    //debug(lv);
    if(lv==limit-1){
        if(notDesired==0){
            X[i-1]=sum;
            parent[sum]=i-1;
        }
        else{
            X[i-1]=-k;
            removed[sum]=1;
        }
        sum+=(1<<lv);
        Y[i-1]=sum;
        parent[sum]=i-1;
        return;
    }
    int treeSize=(1<<(limit-lv-1));
    //debug(treeSize);
    //debug(notDesired);
    if(notDesired>=treeSize){ //Eliminate left child, all unused exits
        explore_PhantomTree(limit,lv+1,sum);
        X[i-1]=-k; //Kill out that exit (connect it to the root)
        Y[i-1]=-(++NEXT_FREE_INDEX);
        createTree(-Y[i-1],limit,lv+1,sum+(1<<lv),notDesired-treeSize);
    }
    else{
        X[i-1]=-(++NEXT_FREE_INDEX);
        Y[i-1]=-(++NEXT_FREE_INDEX);
        createTree(-X[i-1],limit,lv+1,sum,notDesired);
        createTree(-Y[i-1],limit,lv+1,sum+(1<<lv),0);
    }
}
int log_n[400005];
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{ //Create a tree of switches
        memset(parent,0,sizeof(parent));
        memset(removed,0,sizeof(removed));
        memset(moved,0,sizeof(moved));
        int limit=log_n[ destino[i].size() ];
        C[i]=-(++NEXT_FREE_INDEX);
        k=-C[i];
        int notDesired=(1<<limit)-destino[i].size();
        createTree(-C[i],limit,0,0,notDesired);
        connectLeaves((1<<limit),i);
    }
  }
  vector<int> x,y;
  for(int i=0;i<NEXT_FREE_INDEX;i++){
    //debug(i);
    //debug(X[i]);
    //debug(Y[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 52 ms 7908 KB Output is correct
3 Correct 27 ms 7500 KB Output is correct
4 Correct 4 ms 4172 KB Output is correct
5 Correct 16 ms 5324 KB Output is correct
6 Correct 44 ms 9196 KB Output is correct
7 Correct 4 ms 4172 KB Output is correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4172 KB Output is correct
2 Correct 52 ms 7908 KB Output is correct
3 Correct 27 ms 7500 KB Output is correct
4 Correct 4 ms 4172 KB Output is correct
5 Correct 16 ms 5324 KB Output is correct
6 Correct 44 ms 9196 KB Output is correct
7 Correct 4 ms 4172 KB Output is correct
8 Execution timed out 1086 ms 9932 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4172 KB Output is correct
2 Correct 52 ms 7908 KB Output is correct
3 Correct 27 ms 7500 KB Output is correct
4 Correct 4 ms 4172 KB Output is correct
5 Correct 16 ms 5324 KB Output is correct
6 Correct 44 ms 9196 KB Output is correct
7 Correct 4 ms 4172 KB Output is correct
8 Execution timed out 1086 ms 9932 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6476 KB Output is correct
2 Incorrect 55 ms 12480 KB wrong serial number
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6476 KB Output is correct
2 Incorrect 55 ms 12480 KB wrong serial number
3 Halted 0 ms 0 KB -