Submission #468859

#	Time	Username	Problem	Language	Result	Execution time	Memory
468859		vector	Mechanical Doll (IOI18_doll)	C++17	100 / 100	194 ms	32596 KiB

doll

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

void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y);

vector<int> C, X, Y, psum;
unordered_map<int, int> trash;
vector<int> develop(vector<int> x)
{
    int t=x.size();
    vector<int> y(2*t);
    for (int i=0; i<2*t; i+=2) y[i]=x[i/2];
    for (int i=1; i<2*t; i+=2) y[i]=y[i-1]+t;
    return y;
}
void create_circuit(int M, vector<int> A)
{
    int N=A.size(), cnt=1, x=1;
    C.push_back(A[0]);
    for (int i=1; i<N; i++) A[i-1]=A[i];
    A[N-1]=0;
    for (int i=1; i<=M; i++) C.push_back(-1);
    while ((1<<x)<N) x++;

    vector<int> P, Q;
    int y, t=(1<<x);
    X.push_back(0);
    Y.push_back(0);
    psum.resize(t+1);
    for (int i=0; i<t; i++) trash[-i]=-i;
    for (int i=1; i<=M; i++) trash[i]=i;
    for (int i=1; i<t/2; i++) {
        X.push_back(-2*i);
        Y.push_back(-2*i-1);
    }
    for (int i=t/2; i<t; i++) {
        X.push_back(0);
        Y.push_back(0);
    }
    vector<int> v(1, 1);
    while (v.size()!=t) v=develop(v);
    for (int i=0; i<t-A.size(); i++) {
        y=i/2;
        if (i%2==0) X[t/2+y]=-1;
        else Y[t/2+y]=-1;
        psum[v[i]]=1;
    }
    for (int i=1; i<=t; i++) psum[i]+=psum[i-1];
    for (int i=t-A.size(); i<t; i++) {
        y=i/2;
        if (i%2==0) X[t/2+y]=A[v[i]-psum[v[i]]-1];
        else Y[t/2+y]=A[v[i]-psum[v[i]]-1];
    }
    for (int i=t-1; i>1; i--) if (trash[X[i]]==-1 && trash[Y[i]]==-1) trash[-i]=-1;
    for (int i=2; i<t; i++) if (trash[-i]!=-1) trash[-i]=-(++cnt);
    for (int i=1; i<t; i++) if (trash[-i]!=-1 || i==1) {
        P.push_back(trash[X[i]]);
        Q.push_back(trash[Y[i]]);
    }
    answer(C, P, Q);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:43:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |     while (v.size()!=t) v=develop(v);
      |            ~~~~~~~~^~~
doll.cpp:44:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for (int i=0; i<t-A.size(); i++) {
      |                   ~^~~~~~~~~~~

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