Submission #430869

#	Time	Username	Problem	Language	Result	Execution time	Memory
430869		Amylopectin	Mechanical Doll (IOI18_doll)	C++14	37 / 100	96 ms	18404 KiB

doll

#include <iostream>
#include <stdio.h>
#include <vector>
#include "doll.h"
//#include "grader.cpp"
using namespace std;
const int mxn = 4e5 + 10;
int fr[mxn] = {},to[mxn] = {},tw[mxn] = {},cpoi[mxn] = {},sta[mxn] = {};
vector<int> li[mxn] = {};
void create_circuit(int m, vector<int> a)
{
    int n = a.size()+1,i,j,po = 0,ru = 1,cru,k;
    vector<int> c(m + 1),x, y;
//    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 ++;
        }
//        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-1; j++)
        {
            y[cpoi[j - tw[po-1]]] = a[j];
//            fr[li[i][j]] = ru + cpoi[j-tw[po-1]];
//            sta[li[i][j]] = 2;
        }
        y[cpoi[tw[po-1]-1]] = 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;
//}

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