Submission #879603

#	Time	Username	Problem	Language	Result	Execution time	Memory
879603		andrei_boaca	Mechanical Doll (IOI18_doll)	C++17	53 / 100	122 ms	29776 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 build(int st,int dr)
{
    if(st==dr)
        return INF;
    ll lg=dr-st+1;
    if(__builtin_popcount(lg)==1)
    {
        ll mij=(st+dr)/2;
        ll a=build(st,mij);
        ll b=build(mij+1,dr);
        s++;
        lft[s]=a;
        rgt[s]=b;
        return -s;
    }
    ll lsb=(lg&(-lg));
    ll poz=dr-lsb;
    ll a=build(st,poz);
    ll b=build(poz+1,dr);
    s++;
    lft[s]=a;
    rgt[s]=b;
    return -s;
}
int plsmake()
{
    if(v.size()==1)
        return v[0];
    ll lg=v.size();
    while(__builtin_popcount(lg)>1)
        lg++;
    int c=build(0,lg-1);
    vector<pii> ord;
    for(int i=1;i<=lg;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)
{
    n=A.size();
    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.resize(M+1);
    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:80: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]
   80 |     for(int i=0;i<ord.size();i++)
      |                 ~^~~~~~~~~~~
doll.cpp:84:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         if(i+1<v.size())
      |            ~~~^~~~~~~~~
doll.cpp:92: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]
   92 |         if(i+1==ord.size())
      |            ~~~^~~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:110:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for(int i=0;i<A.size();i++)
      |                 ~^~~~~~~~~
doll.cpp:114:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |         if(i+1<A.size())
      |            ~~~^~~~~~~~~

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