제출 #415495

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
415495		baluteshih	자동 인형 (IOI18_doll)	C++14	64.61 / 100	157 ms	9888 KiB

doll

#include "doll.h"
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define pb push_back
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define F first
#define S second
#define ET cout << "\n"
#define MP make_pair
#define MEM(i,j) memset(i,j,sizeof i)
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

vector<int> C,X,Y,pl[100005];
bool state[400005];
const int INF=1e9;

int newnode()
{
    X.pb(INF),Y.pb(INF);
    return -(int)(X.size());
}

int node(int x)
{
    if(x==2) return newnode();
    int tmp=newnode();
    int a=node(x/2),b=node(x/2);
    X[-tmp-1]=a,Y[-tmp-1]=b;
    return tmp;
}

void walk(vector<int> &v,int st)
{
    int k=0;
    int pos=st;
    while(k<v.size())
    {
        state[-pos] = !state[-pos];
        if(state[-pos])
            if(X[-(1+pos)]!=INF) pos=X[-(1+pos)];
            else X[-(1+pos)]=v[k++],pos=st;
        else
            if(Y[-(1+pos)]!=INF) pos=Y[-(1+pos)];
            else Y[-(1+pos)]=v[k++],pos=st;
    }
}

int r_node(vector<int> &v)
{
    int tmp,sz=v.size();
    if(!(sz&(sz-1))) tmp=node(sz);
    else
    {
        int nw=tmp=newnode(),lb=sz&-sz,a;
        for(int i=1<<__lg(sz);i>lb;i>>=1)
        {
            if(v.size()&i)
                a=node(i),X[-nw-1]=a;
            else
                X[-nw-1]=tmp;
            a=newnode(),Y[-nw-1]=a,nw=Y[-nw-1];
        }
        X[-nw-1]=tmp;
        if(lb>1) a=node(lb),Y[-nw-1]=a;
    }
    walk(v,tmp);
    return tmp;
}

void create_circuit(int M, std::vector<int> A) {
    C.resize(M+1);
    C[0]=A[0];
    if(A.size()==1)
        C[1]=0;
    else
    {
        for(int i=0;i+1<A.size();++i)
            A[i]=A[i+1];
        A.back()=0;
        int tmp=r_node(A);
        for(int i=1;i<=M;++i)
            C[i]=tmp;
    }
    int tar = A.size() + __lg(A.size());
    while (X.size() <= tar)
        X.pb(0), Y.pb(0);
    answer(C,X,Y);
}

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

doll.cpp: In function 'void walk(std::vector<int>&, int)':
doll.cpp:41:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     while(k<v.size())
      |           ~^~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:82:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |         for(int i=0;i+1<A.size();++i)
      |                     ~~~^~~~~~~~~
doll.cpp:90:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   90 |     while (X.size() <= tar)
      |            ~~~~~~~~~^~~~~~

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