Submission #297548

#	Time	Username	Problem	Language	Result	Execution time	Memory
297548		eohomegrownapps	Mechanical Doll (IOI18_doll)	C++14	10 / 100	54 ms	9128 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> order;

namespace sim{
int M, N;
std::vector<int> A;

bool answered;
int S;
std::vector<int> IC, IX, IY;

void simulate() {
  int P = 0;
  std::vector<bool> state(S + 1, false);
  int pos = IC[0];
  int k = 0;
  for (;;) {
    //cout<<pos<<endl;
    if (pos < 0) {
      state[-pos] = !state[-pos];
      pos = state[-pos] ? IX[-(1 + pos)] : IY[-(1 + pos)];
    } else {
      if (pos == 0) {
        break;
      }
      //cout<<pos<<'\n';
      if (pos>=1){
        order.push_back(pos);
      }
      pos = IC[pos];
    }
  }
}
}

vector<vector<int>> adjlist;

vector<int> exitto;
vector<int> switchxto;
vector<int> switchyto;

int sind = 0;

// level 0 -- base

//int lind = -1;
int finale = 0;

int ind = 1;

int create(int parent, int level, int num, const vector<int> &seq, int s, int e){
    // returns index of switch
    /*cout<<"make switch "<<-1-sind<<" at level "<<level<<'\n'<<" with num "<<num<<'\n';
    for (int i : seq){
        cout<<i<<' ';
    }cout<<'\n';*/
    /*cout<<seq.size()<<'\n';*/
    if (num==0){
        //cout<<"num is 0"<<'\n';
        if (level==0){
            return (e==finale)?0:-1;
        }
        // make something that counts (1<<level) times before returning
        int firstswitch = sind;
        for (int i = 0; i<level-1; i++){
            // make switch
            // parent: prevconnect
            // x: -1
            // y: sind+1
            switchxto.push_back(1e9);
            switchyto.push_back(1e9);
            switchxto[sind]=-1;
            switchyto[sind]=-1-(sind+1);
            sind++;
        }
        switchxto.push_back(1e9);
        switchyto.push_back(1e9);
        switchxto[sind]=-1;
        switchyto[sind]=(e==finale)?0:-1;
        //lind=sind;
        sind++;
        return -1-firstswitch;
    }
    if (level==0){
        //numleft--;
        ind++;
        return ind-1;
    }

    int switchtouse = sind;
    switchxto.push_back(1e9);
    switchyto.push_back(1e9);
    sind++;

    int sendleft = min((1<<(level-1)),num);
    int sendright = max(0,num-(1<<(level-1)));
    vector<int> left;
    vector<int> right;
    
    int ptr = 0;
    for (int i = 0; i<sendright; i++){
        left.push_back(seq[ptr]);
        right.push_back(seq[ptr+1]);
        ptr+=2;
    }
    for (int i = sendright; i<sendleft; i++){
        left.push_back(seq[ptr]);
        ptr++;
    }

    int cl = create(switchtouse,level-1,sendleft,left,s,(s+e)/2);
    int cr = create(switchtouse,level-1,sendright,right,(s+e)/2+1,e);
    switchxto[switchtouse]=cl;
    switchyto[switchtouse]=cr;
    return -1-switchtouse;
}

void create_circuit(int m, std::vector<int> a) {
    int n = a.size();

    if (n%2!=1){
        n++;
    }
    int level = log2(n-1)+1;
    finale = (1<<level)-1;
    create(0,level,a.size(),a,0,(1<<level)-1);
    /*if (lind!=-1){
        switchyto[lind]=0;
    }*/
    exitto.resize(n+1,-1);
    sim::IC = exitto;
    sim::IX = switchxto;
    sim::IY = switchyto;
    sim::simulate();
    /*for (int i : order){
        cout<<i<<' ';
    }cout<<'\n';*/
    vector<int> ord2ind(order.size()+1);
    for (int i = 0; i<order.size(); i++){
        ord2ind[order[i]]=i;
    }
    for (int i = 0; i<switchxto.size(); i++){
        if (switchxto[i]>=1){
            switchxto[i]=a[ord2ind[switchxto[i]]];
        }
        if (switchyto[i]>=1){
            switchyto[i]=a[ord2ind[switchyto[i]]];
        }
    }
    exitto.resize(m+1,-1);
    /*for (int i : switchxto){
        cout<<i<<' ';
    }cout<<'\n';
    for (int i : switchyto){
        cout<<i<<' ';
    }cout<<'\n';*/
    answer(exitto,switchxto,switchyto);
}

Compilation message (stderr)

doll.cpp: In function 'void sim::simulate()':
doll.cpp:16:7: warning: unused variable 'P' [-Wunused-variable]
   16 |   int P = 0;
      |       ^
doll.cpp:19:7: warning: unused variable 'k' [-Wunused-variable]
   19 |   int k = 0;
      |       ^
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:142:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |     for (int i = 0; i<order.size(); i++){
      |                     ~^~~~~~~~~~~~~
doll.cpp:145:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |     for (int i = 0; i<switchxto.size(); i++){
      |                     ~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 18
• Subtask 6: 0 / 56