oj.uz

Submission #101934

# Submission time Handle Problem Language Result Execution time Memory
101934 2019-03-21T06:06:13 Z daniel920712 Mechanical Doll (IOI18_doll) C++14
100 / 100
 149 ms 12596 KB 
#include "doll.h"
#include <vector>
#include <stdio.h>

using namespace std;
int con[1000005]={0};
int This[1000005]={0};
int m[1000005];
int n[1000005];
int start[1000005]={0};
vector < int > C,x,y;
int X[1000005]={0};
int Y[1000005]={0};
int now=1;
int t[1000005]={0};
int how[1000005]={0};
void build(int N,int one,int here,int what)
{
    if(one==1)
    {
        Y[-here]=0;
        if(N==2) X[-here]=0;
        else X[-here]=what;
    }
    else
    {
        if(N<=one) X[-here]=what;
        else
        {
            X[-here]=(-now);
            now++;
        }
        Y[-here]=(-now);
        now++;
        if(N>one)
        {
            build(N-one,one/2,X[-here],what);
            build(one,one/2,Y[-here],what);
        }
        else build(N,one/2,Y[-here],what);

    }
}
void New(int here,int what)
{
    //printf("%d ",here);
    if(how[-here]%2==0)
    {
        how[-here]++;
        if(X[-here]) New(X[-here],what);
        else X[-here]=what;
    }
    else
    {
        how[-here]++;
        if(Y[-here]) New(Y[-here],what);
        else Y[-here]=what;
    }
}
void create_circuit(int M, vector < int > A)
{
    int N=A.size(),i,temp,t=1,big=0;
    C.push_back(A[0]);
    for(i=1;i<=M;i++) C.push_back(i);
    for(i=0;i<N;i++)
    {
        con[A[i]]++;
        big=max(big,con[A[i]]);
    }
    A.push_back(0);
    if(big<=4)
    {
        for(i=0;i<N;i++)
        {
            if(con[A[i]]==1) C[A[i]]=A[i+1];
            else
            {
                if(!This[A[i]])
                {
                    C[A[i]]=-now;
                    now++;
                    temp=1;
                    while(temp<con[A[i]]) temp*=2;
                    build(con[A[i]],temp/2,C[A[i]],C[A[i]]);
                }
                This[A[i]]++;
                New(C[A[i]],A[i+1]);
            }
        }
    }
    else
    {
       while(t<N) t*=2;

        now++;
        build(N,t/2,-1,-1);
        for(i=0;i<N;i++)
        {
            C[A[i]]=-1;
            //printf("a%d: ",i);
            New(C[A[i]],A[i+1]);
            //printf("\n");
        }
    }



    //for(i=1;i<now;i++) printf("%d %d %d\n",-i,X[i],Y[i]);
    for(i=1;i<now;i++) x.push_back(X[i]);
    for(i=1;i<now;i++) y.push_back(Y[i]);
    answer(C,x,y);

}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 25 ms 2496 KB Output is correct
3 Correct 18 ms 1980 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 1852 KB Output is correct
6 Correct 30 ms 2824 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 25 ms 2496 KB Output is correct
3 Correct 18 ms 1980 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 1852 KB Output is correct
6 Correct 30 ms 2824 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 50 ms 5784 KB Output is correct
9 Correct 50 ms 5528 KB Output is correct
10 Correct 74 ms 8476 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 25 ms 2496 KB Output is correct
3 Correct 18 ms 1980 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 1852 KB Output is correct
6 Correct 30 ms 2824 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 50 ms 5784 KB Output is correct
9 Correct 50 ms 5528 KB Output is correct
10 Correct 74 ms 8476 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 104 ms 12596 KB Output is correct
15 Correct 56 ms 6392 KB Output is correct
16 Correct 85 ms 9560 KB Output is correct
17 Correct 2 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 96 ms 10404 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 236 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 76 ms 7112 KB Output is correct
3 Correct 93 ms 6596 KB Output is correct
4 Correct 122 ms 9996 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 76 ms 7112 KB Output is correct
3 Correct 93 ms 6596 KB Output is correct
4 Correct 122 ms 9996 KB Output is correct
5 Correct 128 ms 11408 KB Output is correct
6 Correct 137 ms 11040 KB Output is correct
7 Correct 134 ms 11224 KB Output is correct
8 Correct 127 ms 10768 KB Output is correct
9 Correct 78 ms 6568 KB Output is correct
10 Correct 129 ms 10660 KB Output is correct
11 Correct 122 ms 10372 KB Output is correct
12 Correct 102 ms 6816 KB Output is correct
13 Correct 79 ms 7736 KB Output is correct
14 Correct 81 ms 7364 KB Output is correct
15 Correct 85 ms 7580 KB Output is correct
16 Correct 3 ms 460 KB Output is correct
17 Correct 88 ms 7384 KB Output is correct
18 Correct 77 ms 7332 KB Output is correct
19 Correct 86 ms 6844 KB Output is correct
20 Correct 149 ms 10636 KB Output is correct
21 Correct 119 ms 10268 KB Output is correct
22 Correct 124 ms 10392 KB Output is correct