Submission #594851

#	Time	Username	Problem	Language	Result	Execution time	Memory
594851		TimDee	Mechanical Doll (IOI18_doll)	C++14	11 / 100	80 ms	9024 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

void create_circuit(int m, vector<int>a) {
    int n=a.size();
    if (n==1) {
        vector<int> c = {a[0], 0}, x, y;
        answer(c,x,y);
    } else if (m==1) {

        int size=1;
        while ((size<<1)<n) size<<=1;
        vector<int> x(2*size-1), y(2*size-1), state(2*size-1,0), c = {1, -1};
        for (int i=1; i<=size-1; ++i) {
            x[i-1] = -(2*i);
            y[i-1] = -(2*i+1);
        }
        for (int i=size-1; i<2*size-1; ++i) x[i]=1;

        int cnt=0, p=0;
        while (cnt<size) {

            //cout<<p<<"->";
            if (p>=size-1) {
                //cout<<"added "<<p<<' '<<cnt<<'\n';
                if (cnt+size<n-1) y[p]=1;
                else y[p]=-1;
                ++cnt;
                p=0;
                continue;
            }

            if (!state[p]) {

                state[p]^=1;
                p<<=1; ++p;

            } else {

                state[p]^=1;
                ++p; p<<=1;

            }

        }
        y[2*size-2]=0;
        answer(c,x,y);

    } else {

        vector<int> c(m+1,0);
        c[0]=a[0];
        for (int i=1; i<n; ++i) {
            c[a[i-1]]=a[i];
        }
        vector<int> x(0), y(0);
        answer(c,x,y);

    }
}

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