oj.uz

Submission #829784

# Submission time Handle Problem Language Result Execution time Memory
829784 2023-08-18T15:00:39 Z vnm06 Mechanical Doll (IOI18_doll) C++14
10 / 100
 1 ms 336 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; 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;
        }
    }
    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
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB wrong serial number
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB wrong serial number
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB wrong serial number
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 304 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 308 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB wrong serial number
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB wrong serial number
2 Halted 0 ms 0 KB -