Submission #430949

#	Time	Username	Problem	Language	Result	Execution time	Memory
430949		Amylopectin	Mechanical Doll (IOI18_doll)	C++14	70.67 / 100	130 ms	20328 KiB

doll

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include "doll.h"
//#include "grader.cpp"
using namespace std;
const int mxn = 4e5 + 10;
struct we
{
    int vaa,ind,sta;
};
bool cmp(const struct we &l,const struct we &r)
{
    return l.vaa < r.vaa;
}
struct we so[mxn] = {};
int fr[mxn] = {},to[mxn] = {},tw[mxn] = {},cpoi[mxn] = {},sta[mxn] = {},aru,cx[mxn] = {},cy[mxn] = {},cso = 0;
vector<int> li[mxn] = {};
int re(int cn,int rva,int la,int coub,int acva)
{
    if(la == 1)
    {
        so[cso] = {acva,cn,0};
        cso ++;
        if(rva == 2)
        {
            so[cso] = {acva + tw[coub],cn,1};
            cso ++;
        }
        return 0;
    }
    int i,fn;
    if(rva <= tw[la-1])
    {
        cx[cn] = aru;
        cy[cn] = 0;
        aru ++;
        re(aru-1,rva,la-1,coub+1,acva);
    }
    else
    {
        cx[cn] = aru;
        cy[cn] = aru + 1;
        aru += 2;
        re(aru-2,tw[la-1],la-1,coub+1,acva);
        re(cy[cn],rva-tw[la-1],la-1,coub+1,acva+tw[coub]);
    }
    return 0;
}
void create_circuit(int m, vector<int> a)
{
    int n = a.size()+1,i,j,po = 0,ru = 1,cru,k,fn;
    vector<int> c(m + 1),x, y;
    aru = 1;
//    C[0] = -1;
//    for (int i = 1; i <= M; ++i) {
//        C[i] = 1;
//    }
//    for (int k = 0; k < N; ++k) {
//        X[k] = Y[k] = A[k];
//    }
    tw[0] = 1;
    for(i=1; i<20; i++)
    {
        tw[i] = tw[i-1] * 2;
    }
//    for(i=0; i<n; i++)
//    {
//        li[a[i]].push_back(i);
//    }
    for(i=0; i<=m; i++)
    {
        c[i] = -1;
    }
//    fr[0] = 0;
//    for(i=1; i<=m; i++)
//    {
//        if(li[i].size() == 0)
//        {
//            c[i] = 0;
//            continue;
//        }
//        po = 0;
        while(tw[po] < n)
        {
            po ++;
        }

    re(0,n-1,po,0,0);
    sort(so,so+cso,cmp);
    fn = 0;
    for(i=1; i<po; i++)
    {
        if(cy[fn] == 0)
        {
            cy[fn] = aru;
            fn = aru;
            aru ++;
        }
        else
        {
            fn = cy[fn];
        }
    }
    for(i=0; i<aru; i++)
    {
        x.push_back(-(cx[i]+1));
        y.push_back(-(cy[i]+1));
    }
    y[fn] = 0;
    for(i=0; i<cso; i++)
    {
        if(so[i].sta == 0)
        {
            x[so[i].ind] = a[i];
        }
        else
        {
            y[so[i].ind] = a[i];
        }
    }
//        if(po == 0)
//        {
//            fr[li[i][0]] = i;
//            to[li[i][0]] = i;
//            continue;
//        }
//        for(j=0; j<li[i].size(); j++)
//        {
//            to[li[i][j]] = i;
//        }
//        cru = 0;
////        c[i] = -ru;
//        cpoi[0] = cru;
//        x.push_back(-1);
//        y.push_back(-1);
//        for(j=0; j<po-1; j++)
//        {
//            for(k=0; k<tw[j]; k++)
//            {
//                x[ru+cpoi[k]-1] = -(ru + cru + 1);
//                y[ru+cpoi[k]-1] = -(ru + cru + 2);
//                cpoi[k] = cru + 1;
//                cpoi[k+tw[j]] = cru + 2;
//                x.push_back(-1);
//                y.push_back(-1);
//                x.push_back(-1);
//                y.push_back(-1);
//                cru += 2;
//            }
//        }
//        for(j=0; j<tw[po-1]; j++)
//        {
//            x[cpoi[j]] = a[j];
////            fr[li[i][j]] = ru + cpoi[j];
////            sta[li[i][j]] = 1;
//        }
//        for(j=tw[po-1]; j<n; j++)
//        {
//            y[cpoi[j - tw[po-1]]] = a[j];
////            fr[li[i][j]] = ru + cpoi[j-tw[po-1]];
////            sta[li[i][j]] = 2;
//        }
//
//
//
//    if(tw[po] != n)
//    {
//        y[cpoi[tw[po-1]-1]] = 0;
//    }
//    else
//    {
//        cru ++;
//        for(i=0; i<=m; i++)
//        {
//            c[i] = -(cru + 1);
//        }
//        for(i=0; i<cru; i++)
//        {
//            if(x[i] == -1)
//            {
//                x[i] = -(cru + 1);
//            }
//            if(y[i] == -1)
//            {
//                y[i] = -(cru + 1);
//            }
//        }
//
//        for(i=cru; i<=cru + po; i++)
//        {
//            x.push_back(-(cru+1));
//            y.push_back(-(i+2));
////            x[i] = -1;
////            y[i] = i+1;
//        }
//        x[cru] = -1;
//        y[cru + po] = 0;
//    }

//        for(j=li[i].size()-1; j<tw[po]-1; j++)
//        {
//            y[ru+cpoi[j-tw[po-1]]-1] = -ru;
//        }
//        fr[li[i][li[i].size()-1]] = ru + cpoi[tw[po-1]-1];
//        sta[li[i][li[i].size()-1]] = 2;
//        ru += cru+1;
//    }
//    c[0] = a[0];
//    for(i=0; i<n-1; i++)
//    {
//        if(sta[i] == 0)
//        {
//            c[fr[i]] = a[i+1];
//        }
//        else if(sta[i] == 1)
//        {
//            x[fr[i]-1] = a[i+1];
//        }
//        else
//        {
//            y[fr[i]-1] = a[i+1];
//        }
//    }
//    if(sta[n-1] == 0)
//    {
//        c[fr[n-1]] = 0;
//    }
//    else if(sta[n-1] == 1)
//    {
//        x[fr[n-1]-1] = 0;
//    }
//    else
//    {
//        y[fr[n-1]-1] = 0;
//    }
    answer(c, x, y);
}
//int main()
//{
//    cout << "Hello world!" << endl;
//    return 0;
//}

Compilation message (stderr)

doll.cpp: In function 'int re(int, int, int, int, int)':
doll.cpp:33:9: warning: unused variable 'i' [-Wunused-variable]
   33 |     int i,fn;
      |         ^
doll.cpp:33:11: warning: unused variable 'fn' [-Wunused-variable]
   33 |     int i,fn;
      |           ^~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:53:26: warning: unused variable 'j' [-Wunused-variable]
   53 |     int n = a.size()+1,i,j,po = 0,ru = 1,cru,k,fn;
      |                          ^
doll.cpp:53:35: warning: unused variable 'ru' [-Wunused-variable]
   53 |     int n = a.size()+1,i,j,po = 0,ru = 1,cru,k,fn;
      |                                   ^~
doll.cpp:53:42: warning: unused variable 'cru' [-Wunused-variable]
   53 |     int n = a.size()+1,i,j,po = 0,ru = 1,cru,k,fn;
      |                                          ^~~
doll.cpp:53:46: warning: unused variable 'k' [-Wunused-variable]
   53 |     int n = a.size()+1,i,j,po = 0,ru = 1,cru,k,fn;
      |                                              ^

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