Submission #880576

#	Time	Username	Problem	Language	Result	Execution time	Memory
880576		andrei_boaca	Mechanical Doll (IOI18_doll)	C++17	100 / 100	104 ms	19744 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[500005],rgt[500005];
int s;
int state[500005];
int added=0;
int build(int st,int dr,int a,int b)
{
    if(dr<a||st>b)
        return -INF;
    if(st==dr)
        return INF;
    int mij=(st+dr)/2;
    int l=build(st,mij,a,b);
    int r=build(mij+1,dr,a,b);
    s++;
    lft[s]=l;
    rgt[s]=r;
    return -s;
}
int plsmake()
{
    if(v.size()==1)
        return v[0];
    int lg=v.size();
    int L=lg;
    while(__builtin_popcount(L)>1)
        L++;
    int root=build(1,L,L-lg+1,L);
    vector<pii> ord;
    for(int z=1;z<=L;z++)
    {
        int nod=abs(root);
        while(true)
        {
            if(state[nod]==0)
            {
                state[nod]^=1;
                if(lft[nod]==-INF)
                    break;
                if(lft[nod]==INF)
                {
                    ord.push_back({nod,0});
                    break;
                }
                nod=-lft[nod];
                continue;
            }
            else
            {
                state[nod]^=1;
                if(rgt[nod]==-INF)
                    break;
                if(rgt[nod]==INF)
                {
                    ord.push_back({nod,1});
                    break;
                }
                nod=-rgt[nod];
                continue;
            }
        }
    }
    for(int i=0;i<v.size();i++)
    {
        int nod=ord[i].first,dir=ord[i].second;
        if(dir==0)
            lft[nod]=v[i];
        else
            rgt[nod]=v[i];
    }
    return root;
}
void create_circuit(int M, std::vector<int> A)
{
    C.resize(M+1);
    n=A.size();
    C[0]=A[0];
    for(int i=1;i<A.size();i++)
        v.push_back(A[i]);
    v.push_back(0);
    int r=plsmake();
    for(int i=1;i<=M;i++)
        C[i]=r;
    for(int i=1;i<=s;i++)
    {
        if(lft[i]==-INF)
            lft[i]=r;
        X.push_back(lft[i]);
        Y.push_back(rgt[i]);
    }
    answer(C,X,Y);
}

Compilation message (stderr)

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

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