제출 #431589

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
431589		Enkognit	자동 인형 (IOI18_doll)	C++14	43 / 100	243 ms	25524 KiB

doll

#include <bits/stdc++.h>
#include "doll.h"
#define ll long long
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define pll pair<ll,ll>
#define all(v) v.begin(),v.end()

using namespace std;

ll n, m, s, nxt[100005], k=0;
pll a[400005];
vector<ll> v[100005];
bool tt[400005];

ll build(int l,int r)
{
    if (l==r)
    {
        return 0;
    }
    s--;
    ll nw=s;
    int w=(l+r)/2;
    a[-nw].fi=build(l,w);
    a[-nw].se=build(w+1,r);
    return nw;
}

ll dfs(int nw,int l,int r,int k)
{
    if (l==r)
    {
        return k;
    }
    int w=(l+r)/2;
    if (!tt[nw])
    {
        ll o=dfs(a[-nw].fi, l, w, k);
        if (o!=-1e18) a[-nw].fi=o;
    }else
    {
        ll o=dfs(a[-nw].se, w+1, r, k);
        if (o!=-1e18) a[-nw].se=o;
    }
    tt[nw]^=1;
    return -1e18;
}

bool zz[1000005];

void create_circuit(int m, vector<int> aa) {
    s=0;
    for (int i = 1; i <= 1e6; i*=2) zz[i]=1;
    aa.pb(0);
    for (int i = 0; i < aa.size()-1; i++)
    {
        v[aa[i]].pb(aa[i+1]);
    }
    nxt[0]=aa[0];
    for (int i = 1; i <= m; i++)
        if (v[i].size()>0)
        {
            if (v[i].size()==1)
                nxt[i]=v[i][0]; else
            {
                ll tt=0;
                reverse(all(v[i]));
                if (!zz[v[i].size()])
                {
                    s--;
                    a[-s].fi=s;
                    a[-s].se=0;
                    tt=s;
                }

                while (!zz[v[i].size()])
                {
                    v[i].pb(s);
                }
                reverse(all(v[i]));

                ll o=build(0,v[i].size()-1);
                nxt[i]=o;
                if (tt!=0) a[-tt].se=o;

                for (int j = 0; j < v[i].size(); j++)
                    dfs(o, 0, v[i].size()-1, v[i][j]);
            }
        }
    std::vector<int> X, Y, C;
    X.resize(-s);
    Y.resize(-s);
    C.resize(m+1);
    for (int i = 0; i <= m; i++)
        C[i]=(int)nxt[i];
    for (int i = -1; i >= s; i--)
        X[-i-1]=(int)a[-i].fi, Y[-i-1]=(int)a[-i].se;

    /*cout << m << " " << aa.size() << "\n";
    for (int i = 0; i < aa.size(); i++)cout << aa[i] << " ";
    cout << "\n";

    for (int i = 0; i < C.size(); i++)
        cout << C[i] << " ";
    cout << "\n";
    for (int i = 0; i < X.size(); i++)
        cout << X[i] << " ";
    cout << "\n";
    for (int i = 0; i < Y.size(); i++)
        cout << Y[i] << " ";
    cout << "\n";*/
    answer(C, X, Y);
}

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

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:58:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for (int i = 0; i < aa.size()-1; i++)
      |                     ~~^~~~~~~~~~~~~
doll.cpp:89:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |                 for (int j = 0; j < v[i].size(); j++)
      |                                 ~~^~~~~~~~~~~~~

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