제출 #284573

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
284573		MKopchev	자동 인형 (IOI18_doll)	C++14	47 / 100	186 ms	10352 KiB

doll

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

const int nmax=1e6+42;

int n;

vector<int> X,Y;

int pointer=0;

int stop;

bool type[nmax];

void push(int node,int val)
{
    //cout<<"push "<<node<<" "<<val<<endl;

    if(node<stop)
    {
        int to=-X[node];

        if(type[node]==1)to=-Y[node];

        type[node]=!type[node];

        push(to,val);
        return;
    }
    else
    {
        if(type[node]==0)X[node]=val;
        else Y[node]=val;

        type[node]=!type[node];
        return;
    }
}
/*
void answer(vector<int> c,vector<int> x,vector<int> y)
{
    cout<<c.size()<<" "<<x.size()<<" "<<y.size()<<endl;

    cout<<"c: ";for(auto k:c)cout<<k<<" ";cout<<endl;
    cout<<"x: ";for(auto k:x)cout<<k<<" ";cout<<endl;
    cout<<"y: ";for(auto k:y)cout<<k<<" ";cout<<endl;
}
*/
vector<int> C={};

void create_circuit(int M, std::vector<int> A)
{
    int orig_n=A.size();

    n=A.size();

    for(int j=0;j<=M;j++)
        C.push_back(-1);

    C[0]=A[0];

    A.erase(A.begin(),A.begin()+1);
    n--;

    int k=1;

    while((1<<k)<n+1)k++;

    while(n+1<(1<<k))
    {
        A.push_back(-1);
        n++;
    }

    A.push_back(0);
    n++;

    //for(auto k:A)cout<<k<<" ";cout<<endl;

    stop=(1<<(k-1));

    for(int i=0;i<(1<<k);i++)
    {
        X.push_back(-1);
        Y.push_back(-1);
    }

    for(int i=1;i<(1<<(k-1));i++)
    {
        X[i]=-(2*i);
        Y[i]=-(2*i+1);
    }

    for(int i=0;i<n;i++)
    {
        push(1,A[i]);
    }

    for(int i=0;i<X.size();i++)
        assert(type[i]==0);

    X.erase(X.begin(),X.begin()+1);

    Y.erase(Y.begin(),Y.begin()+1);

    answer(C,X,Y);
}

컴파일 시 표준 에러 (stderr) 메시지

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:101:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for(int i=0;i<X.size();i++)
      |                 ~^~~~~~~~~
doll.cpp:55:9: warning: unused variable 'orig_n' [-Wunused-variable]
   55 |     int orig_n=A.size();
      |         ^~~~~~

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