oj.uz

Submission #101828

# Submission time Handle Problem Language Result Execution time Memory
101828 2019-03-20T12:14:13 Z daniel920712 Mechanical Doll (IOI18_doll) C++14
53 / 100
 171 ms 15896 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};
void build(int N,int here,int n,int all,int x)
{
    //printf("%d %d %d %d\n",N,here,n,all);
    if(n==all-1)
    {
        if(N%2) Y[-here]=x;
        else X[-here]=x;
        return ;
    }
    if(N%2)
    {
        if(!Y[-here])
        {
            Y[-here]=-now;
            now++;
        }
        build(N/2,Y[-here],n+1,all,x);
    }
    else
    {
        if(!X[-here])
        {
            X[-here]=-now;
            now++;
        }
        build(N/2,X[-here],n+1,all,x);
    }
}
void create_circuit(int M, vector < int > A)
{
    int N=A.size(),i,temp;
    C.push_back(A[0]);
    for(i=1;i<=M;i++) C.push_back(i);
    for(i=0;i<N;i++) con[A[i]]++;
    A.push_back(0);
    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++;
                t[A[i]]=0;
                temp=1;
                while(temp<con[A[i]])
                {
                    temp*=2;
                    t[A[i]]++;
                }
                start[A[i]]=temp-con[A[i]];
                for(int j=0;j<temp;j++) build(j,C[A[i]],0,t[A[i]],C[A[i]]);

            }
            build(This[A[i]]+start[A[i]],C[A[i]],0,t[A[i]],A[i+1]);
            This[A[i]]++;
        }




    }

    //for(auto i:C) printf("%d ",i);
    //printf("\n");
    //for(i=1;i<now;i++) printf("%d %d\n",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 34 ms 2476 KB Output is correct
3 Correct 18 ms 1980 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 14 ms 1804 KB Output is correct
6 Correct 27 ms 2740 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 34 ms 2476 KB Output is correct
3 Correct 18 ms 1980 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 14 ms 1804 KB Output is correct
6 Correct 27 ms 2740 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 58 ms 6160 KB Output is correct
9 Correct 54 ms 6060 KB Output is correct
10 Correct 74 ms 8960 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 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 34 ms 2476 KB Output is correct
3 Correct 18 ms 1980 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 14 ms 1804 KB Output is correct
6 Correct 27 ms 2740 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 58 ms 6160 KB Output is correct
9 Correct 54 ms 6060 KB Output is correct
10 Correct 74 ms 8960 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 95 ms 12316 KB Output is correct
15 Correct 54 ms 6312 KB Output is correct
16 Correct 84 ms 9504 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 88 ms 10516 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 332 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 332 KB Output is partially correct
2 Correct 69 ms 6664 KB Output is correct
3 Partially correct 117 ms 9788 KB Output is partially correct
4 Partially correct 139 ms 10780 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 332 KB Output is partially correct
2 Correct 69 ms 6664 KB Output is correct
3 Partially correct 117 ms 9788 KB Output is partially correct
4 Partially correct 139 ms 10780 KB Output is partially correct
5 Partially correct 171 ms 12928 KB Output is partially correct
6 Partially correct 142 ms 14448 KB Output is partially correct
7 Partially correct 131 ms 13932 KB Output is partially correct
8 Partially correct 136 ms 15312 KB Output is partially correct
9 Partially correct 120 ms 10124 KB Output is partially correct
10 Partially correct 159 ms 15380 KB Output is partially correct
11 Partially correct 170 ms 15896 KB Output is partially correct
12 Partially correct 100 ms 10516 KB Output is partially correct
13 Partially correct 81 ms 9588 KB Output is partially correct
14 Partially correct 78 ms 9136 KB Output is partially correct
15 Partially correct 75 ms 8460 KB Output is partially correct
16 Partially correct 4 ms 588 KB Output is partially correct
17 Partially correct 82 ms 8200 KB Output is partially correct
18 Partially correct 87 ms 8160 KB Output is partially correct
19 Partially correct 92 ms 8832 KB Output is partially correct
20 Partially correct 135 ms 11052 KB Output is partially correct
21 Partially correct 144 ms 13620 KB Output is partially correct
22 Partially correct 119 ms 11248 KB Output is partially correct