Submission #431553

#	Time	Username	Problem	Language	Result	Execution time	Memory
431553		Enkognit	Mechanical Doll (IOI18_doll)	C++14	2 / 100	44 ms	11800 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>

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--;
    int w=(l+r)/2;
    a[-s].fi=build(l,w);
    a[-s].se=build(w+1,r);
    return s;
}

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!=-1) a[-nw].fi=o;
    }else
    {
        ll o=dfs(a[-nw].se, w+1, r, k);
        if (o!=-1) a[-nw].se=o;
    }
    tt[nw]^=1;
    return -1;
}

void create_circuit(int m, vector<int> aa) {
    s=0;
    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 o=build(0,v[i].size()-1);
                nxt[i]=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;

    /*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);
}

Compilation message (stderr)

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

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