Submission #880546

#	Time	Username	Problem	Language	Result	Execution time	Memory
880546		andrei_boaca	Mechanical Doll (IOI18_doll)	C++17	72 / 100	124 ms	29636 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int n;
const int INF=1e9;
vector<int> vecini[100005];
vector<int> C,X,Y;
vector<int> v;
int lft[5000005],rgt[5000005];
int s;
int state[5000005];
int added=0;
int build(int lg)
{
    if(lg==1)
        return INF;
    added+=lg%2;
    lg+=lg%2;
    int a=build(lg/2);
    int b=build(lg/2);
    s++;
    lft[s]=a;
    rgt[s]=b;
    return -s;
}
int plsmake()
{
    if(v.size()==1)
        return v[0];
    ll lg=v.size();
    added=0;
    int c=build(lg);
    vector<pii> ord;
    for(int i=1;i<=lg+added;i++)
    {
        int nod=c;
        while(true)
        {
            nod=abs(nod);
            if(state[nod]==0)
            {
                if(lft[nod]==INF)
                {
                    ord.push_back({nod,0});
                    state[nod]^=1;
                    break;
                }
                state[nod]=1;
                nod=lft[nod];
                continue;
            }
            else
            {
                if(rgt[nod]==INF)
                {
                    ord.push_back({nod,1});
                    state[nod]^=1;
                    break;
                }
                state[nod]=0;
                nod=rgt[nod];
                continue;
            }
        }
    }
    for(int i=0;i<ord.size();i++)
    {
        int who=ord[i].first;
        int dir=ord[i].second;
        if(i+1<v.size())
        {
            if(dir==0)
                lft[who]=v[i];
            else
                rgt[who]=v[i];
            continue;
        }
        if(i+1==ord.size())
        {
            if(dir==0)
                lft[who]=v.back();
            else
                rgt[who]=v.back();
            continue;
        }
        if(dir==0)
            lft[who]=c;
        else
            rgt[who]=c;
    }
    return c;
}
void create_circuit(int M, std::vector<int> A)
{
    C.resize(M+1);
    n=A.size();
    if(M==1)
    {
        C[0]=A[0];
        if(n==1)
        {
            C[1]=0;
            answer(C,X,Y);
            return;
        }
        if(n==2)
        {
            C[1]=-1;
            X.push_back(1);
            Y.push_back(0);
            answer(C,X,Y);
            return;
        }
        C[1]=-1;
        vector<int> bits;
        n--;
        int aux=n;
        while(aux!=0)
        {
            bits.push_back(aux%2);
            aux/=2;
        }
        reverse(bits.begin(),bits.end());
        for(int i=0;i<bits.size();i++)
        {
            s++;
            if(bits[i]==1)
                lft[s]=1;
            else
                lft[s]=-1;
            if(i+1<bits.size())
                rgt[s]=-(s+1);
            else
                rgt[s]=0;
        }
        for(int i=1;i<=s;i++)
        {
            X.push_back(lft[i]);
            Y.push_back(rgt[i]);
        }
        answer(C,X,Y);
        return;
    }
    if(n==16)
    {
        C[0]=A[0];
        for(int i=1;i<A.size();i++)
            v.push_back(A[i]);
        v.push_back(0);
        int c=plsmake();
        for(int i=1;i<=M;i++)
            C[i]=c;
        for(int i=1;i<=s;i++)
        {
            X.push_back(lft[i]);
            Y.push_back(rgt[i]);
        }
        answer(C,X,Y);
        return;
    }
    for(int i=0;i<A.size();i++)
    {
        int x=A[i];
        int nxt=0;
        if(i+1<A.size())
            nxt=A[i+1];
        vecini[x].push_back(nxt);
    }
    C[0]=A[0];
    for(int i=1;i<=M;i++)
    {
        if(vecini[i].empty())
        {
            C[i]=0;
            continue;
        }
        else
        {
            v=vecini[i];
            C[i]=plsmake();
        }
    }
    for(int i=1;i<=s;i++)
    {
        X.push_back(lft[i]);
        Y.push_back(rgt[i]);
    }
    /*for(int i=0;i<C.size();i++)
        cout<<C[i]<<' ';
    cout<<'\n';
    for(int i=1;i<=s;i++)
        cout<<-i<<' '<<X[i-1]<<' '<<Y[i-1]<<'\n';*/
    answer(C,X,Y);
}

Compilation message (stderr)

doll.cpp: In function 'int plsmake()':
doll.cpp:69:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for(int i=0;i<ord.size();i++)
      |                 ~^~~~~~~~~~~
doll.cpp:73:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         if(i+1<v.size())
      |            ~~~^~~~~~~~~
doll.cpp:81:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         if(i+1==ord.size())
      |            ~~~^~~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:127:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |         for(int i=0;i<bits.size();i++)
      |                     ~^~~~~~~~~~~~
doll.cpp:134:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |             if(i+1<bits.size())
      |                ~~~^~~~~~~~~~~~
doll.cpp:150:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |         for(int i=1;i<A.size();i++)
      |                     ~^~~~~~~~~
doll.cpp:164:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |     for(int i=0;i<A.size();i++)
      |                 ~^~~~~~~~~
doll.cpp:168:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |         if(i+1<A.size())
      |            ~~~^~~~~~~~~

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