Submission #197216

#	Time	Username	Problem	Language	Result	Execution time	Memory
197216		stefdasca	Mechanical Doll (IOI18_doll)	C++14	6 / 100	95 ms	12100 KiB

doll

#include "doll.h"
#include<bits/stdc++.h>

using namespace std;

vector<int> adj[100002];
int adja[200002], adjb[200002];

int ord[200002];
bool state[200002];
int nxt;
void dfs(int nod, int rem)
{
    if(rem == 0)
        return;
    --rem;
    if(rem)
    {
        ++nxt;
        adja[-ord[nod]] = ord[nxt];
        dfs(nxt, rem/2 + rem%2);
    }
    if(rem >= 2)
    {
        ++nxt;
        adjb[-ord[nod]] = ord[nxt];
        dfs(nxt, rem / 2);
    }
}
void dfs2(int nod, int val)
{
    if(state[-ord[nod]] == 0)
    {
        state[-ord[nod]] = 1;
        if(!adja[-ord[nod]])
        {
            adja[-ord[nod]] = val;
            return;
        }
        else
            dfs2(-adja[-ord[nod]], val);
    }
    else
    {
        state[-ord[nod]] = 0;
        if(!adjb[-ord[nod]])
        {
            adjb[-ord[nod]] = val;
            return;
        }
        else
            dfs2(-adjb[-ord[nod]], val);
    }
}
void build(int nod, int fi)
{
    for(int i = fi + 1; i < fi + adj[nod].size(); ++i)
        ord[i] = i * (-1);
    nxt = fi + 1;
    dfs(fi + 1, adj[nod].size() - 1);
    for(int i = 0; i < adj[nod].size(); ++i)
        dfs2(fi + 1, adj[nod][i]);

}
void create_circuit(int M, vector<int> A)
{
    int N = A.size();
    vector<int> C(M + 1);
    C[0] = A[0];
    for(int i = 0; i < A.size(); ++i)
    {
        if(i + 1 == A.size())
            adj[A[i]].push_back(0);
        else
            adj[A[i]].push_back(A[i+1]);
    }
    int sw = 0;
    for(int i = 1; i <= M; ++i)
    {
        if(adj[i].size() == 0)
            C[i] = 0;
        else
            if(adj[i].size() == 1)
                C[i] = adj[i][0];
            else
            {
                C[i] = -(sw + 1);
                build(i, sw);
                sw += adj[i].size() - 1;
            }
    }
    vector<int> X(sw), Y(sw);
    for(int k = 0; k < sw; ++k)
    {
        X[k] = adja[k + 1];
        Y[k] = adjb[k + 1];
    }
    /*
    for(int i = 0; i <= M; ++i)
        cout << C[i] << " ";
    cout << '\n';
    for(int k = 0; k < sw; ++k)
        cout << X[k] << " " << Y[k] << '\n';
    */
    answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void build(int, int)':
doll.cpp:57:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(int i = fi + 1; i < fi + adj[nod].size(); ++i)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~
doll.cpp:61:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for(int i = 0; i < adj[nod].size(); ++i)
      |                    ~~^~~~~~~~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:70:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for(int i = 0; i < A.size(); ++i)
      |                    ~~^~~~~~~~~~
doll.cpp:72:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         if(i + 1 == A.size())
      |            ~~~~~~^~~~~~~~~~~
doll.cpp:67:9: warning: unused variable 'N' [-Wunused-variable]
   67 |     int N = A.size();
      |         ^

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