oj.uz

Submission #829807

# Submission time Handle Problem Language Result Execution time Memory
829807 2023-08-18T15:09:19 Z vnm06 Mechanical Doll (IOI18_doll) C++14
100 / 100
 91 ms 11028 KB 
#include<bits/stdc++.h>
#include "doll.h"
using namespace std;

bool st2(int n)
{
    return n==(n&(-n));
}

vector<int> C, D;
vector<int> X, Y;

int brn=0;
int ty[1000005];
void dfs(int pos)
{
    while(1)
    {
        ///cout<<pos<<endl;
    if(pos>=0) pos=C[pos];
    else
    {
        if(brn==D.size()) return;
        ty[-pos-1]^=1;
        if(ty[-pos-1]==1)
        {
            if(!X[-pos-1])
            {
                X[-pos-1]=D[brn];
                pos=D[brn];
                brn++;
            }
            else pos=X[-pos-1];
        }
        else
        {
            if(!Y[-pos-1])
            {
                Y[-pos-1]=D[brn];
                pos=D[brn];
                brn++;
            }
            else pos=Y[-pos-1];
        }
    }
    }
}


void create_circuit(int M, std::vector<int> A)
{
    C.resize(M+1);
    D=A;
    for (int i = 0; i <= M; ++i) C[i]=-1;
    int N = A.size();
    int brb=1, n2=N;
    while(n2!=1)
    {
        brb++;
        n2/=2;
    }
    ///cout<<brb<<endl;
    X.resize(N+brb);
    Y.resize(N+brb);
    int tpos=brb+1;
    for(int i=0; i<brb-1; i++)
    {
        int st2=(1<<(brb-i-1));
        ///cout<<st2<<"  ";
        ///cout<<tpos<<endl;
        if(st2&N)
        {
            X[i]=-tpos;
            Y[i]=-i-2;
            for(int j=tpos; j<tpos+st2/2-1; j++)
            {
                X[j-1]=-(2*(j-tpos+1)+tpos-1);
                Y[j-1]=-(2*(j-tpos+1)+tpos);
            }
            tpos+=st2-1;
        }
        else
        {
            X[i]=-1;
            Y[i]=-i-2;
        }
    }
    if(N%2==0) {X[brb-1]=-1;}
    Y[brb-1]=0;
    dfs(0);
    X.resize(tpos-1);
    Y.resize(tpos-1);
    ///for(int i=0; i<X.size(); i++) cout<<X[i]<<" "<<Y[i]<<endl;
    answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void dfs(int)':
doll.cpp:23:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         if(brn==D.size()) return;
      |            ~~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 31 ms 4484 KB Output is correct
3 Correct 28 ms 4124 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 8 ms 1492 KB Output is correct
6 Correct 43 ms 6116 KB Output is correct
7 Correct 0 ms 308 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 31 ms 4484 KB Output is correct
3 Correct 28 ms 4124 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 8 ms 1492 KB Output is correct
6 Correct 43 ms 6116 KB Output is correct
7 Correct 0 ms 308 KB Output is correct
8 Correct 53 ms 7228 KB Output is correct
9 Correct 62 ms 7648 KB Output is correct
10 Correct 82 ms 11028 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 31 ms 4484 KB Output is correct
3 Correct 28 ms 4124 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 8 ms 1492 KB Output is correct
6 Correct 43 ms 6116 KB Output is correct
7 Correct 0 ms 308 KB Output is correct
8 Correct 53 ms 7228 KB Output is correct
9 Correct 62 ms 7648 KB Output is correct
10 Correct 82 ms 11028 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 85 ms 10568 KB Output is correct
15 Correct 52 ms 6812 KB Output is correct
16 Correct 79 ms 10456 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 300 KB Output is correct
20 Correct 81 ms 10780 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 48 ms 6376 KB Output is correct
3 Correct 51 ms 6388 KB Output is correct
4 Correct 88 ms 9544 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 48 ms 6376 KB Output is correct
3 Correct 51 ms 6388 KB Output is correct
4 Correct 88 ms 9544 KB Output is correct
5 Correct 91 ms 10272 KB Output is correct
6 Correct 78 ms 10184 KB Output is correct
7 Correct 83 ms 10248 KB Output is correct
8 Correct 81 ms 9852 KB Output is correct
9 Correct 46 ms 6384 KB Output is correct
10 Correct 73 ms 9864 KB Output is correct
11 Correct 73 ms 9544 KB Output is correct
12 Correct 58 ms 6312 KB Output is correct
13 Correct 50 ms 6656 KB Output is correct
14 Correct 51 ms 6696 KB Output is correct
15 Correct 51 ms 6864 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 46 ms 6320 KB Output is correct
18 Correct 47 ms 6384 KB Output is correct
19 Correct 51 ms 6380 KB Output is correct
20 Correct 74 ms 9636 KB Output is correct
21 Correct 74 ms 9508 KB Output is correct
22 Correct 73 ms 9548 KB Output is correct