oj.uz

Submission #297632

# Submission time Handle Problem Language Result Execution time Memory
297632 2020-09-11T16:55:55 Z eohomegrownapps Mechanical Doll (IOI18_doll) C++14
60.6729 / 100
 225 ms 12180 KB 
#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=400005;
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==1){
        vector<int> v(m+1);
        v[0]=a[0];
        v[a[0]]=0;
        answer(v,vector<int>(),vector<int>());
        return;
    }
    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

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:148:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |     for (int i = 0; i<order.size(); i++){
      |                     ~^~~~~~~~~~~~~
doll.cpp:151:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |     for (int i = 0; i<switchxto.size(); i++){
      |                     ~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

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

Subtask #2
0 / 4.0

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

Subtask #3
0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
12.3258440412 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 332 KB Output is partially correct
2 Correct 113 ms 8660 KB Output is correct
3 Partially correct 117 ms 8304 KB Output is partially correct
4 Partially correct 177 ms 11500 KB Output is partially correct

Subtask #6
38.3470703504 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 332 KB Output is partially correct
2 Correct 113 ms 8660 KB Output is correct
3 Partially correct 117 ms 8304 KB Output is partially correct
4 Partially correct 177 ms 11500 KB Output is partially correct
5 Partially correct 225 ms 12180 KB Output is partially correct
6 Partially correct 186 ms 11844 KB Output is partially correct
7 Partially correct 222 ms 11928 KB Output is partially correct
8 Partially correct 208 ms 11736 KB Output is partially correct
9 Partially correct 124 ms 8328 KB Output is partially correct
10 Partially correct 188 ms 11704 KB Output is partially correct
11 Partially correct 181 ms 11484 KB Output is partially correct
12 Partially correct 119 ms 8544 KB Output is partially correct
13 Correct 119 ms 9156 KB Output is correct
14 Partially correct 120 ms 8952 KB Output is partially correct
15 Partially correct 146 ms 8944 KB Output is partially correct
16 Partially correct 5 ms 588 KB Output is partially correct
17 Correct 130 ms 8248 KB Output is correct
18 Correct 120 ms 8948 KB Output is correct
19 Partially correct 147 ms 8584 KB Output is partially correct
20 Partially correct 181 ms 11592 KB Output is partially correct
21 Partially correct 208 ms 11520 KB Output is partially correct
22 Partially correct 187 ms 11564 KB Output is partially correct