oj.uz

Submission #879626

# Submission time Handle Problem Language Result Execution time Memory
879626 2023-11-27T18:43:45 Z andrei_boaca Mechanical Doll (IOI18_doll) C++17
53 / 100
 132 ms 29616 KB 
#include "doll.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int n;
const int INF=1e9;
vector<int> vecini[100005];
vector<int> C,X,Y;
vector<int> v;
int lft[5000005],rgt[5000005];
int s;
int state[5000005];
int added=0;
int build(int lg)
{
    if(lg==1)
        return INF;
    added+=lg%2;
    lg+=lg%2;
    int a=build(lg/2);
    int b=build(lg/2);
    s++;
    lft[s]=a;
    rgt[s]=b;
    return -s;
}
int plsmake()
{
    if(v.size()==1)
        return v[0];
    ll lg=v.size();
    added=0;
    int c=build(lg);
    vector<pii> ord;
    for(int i=1;i<=lg+added;i++)
    {
        int nod=c;
        while(true)
        {
            nod=abs(nod);
            if(state[nod]==0)
            {
                if(lft[nod]==INF)
                {
                    ord.push_back({nod,0});
                    state[nod]^=1;
                    break;
                }
                state[nod]=1;
                nod=lft[nod];
                continue;
            }
            else
            {
                if(rgt[nod]==INF)
                {
                    ord.push_back({nod,1});
                    state[nod]^=1;
                    break;
                }
                state[nod]=0;
                nod=rgt[nod];
                continue;
            }
        }
    }
    for(int i=0;i<ord.size();i++)
    {
        int who=ord[i].first;
        int dir=ord[i].second;
        if(i+1<v.size())
        {
            if(dir==0)
                lft[who]=v[i];
            else
                rgt[who]=v[i];
            continue;
        }
        if(i+1==ord.size())
        {
            if(dir==0)
                lft[who]=v.back();
            else
                rgt[who]=v.back();
            continue;
        }
        if(dir==0)
            lft[who]=c;
        else
            rgt[who]=c;
    }
    return c;
}
void create_circuit(int M, std::vector<int> A)
{
    C.resize(M+1);
    n=A.size();
    /*if(M==1)
    {
        C[0]=1;
        if(n==1)
        {
            answer(C,X,Y);
            return;
        }
        s=1;
        C[1]=-s;
        for(int i=1;i<A.size();i++)
        {
            lft[s]=1;
            if(i+1==A.size())
                rgt[s]=0;
            else
            {
                rgt[s]=-(s+1);
                s++;
            }
        }
        for(int i=1;i<=s;i++)
        {
            X.push_back(lft[i]);
            Y.push_back(rgt[i]);
        }
        answer(C,X,Y);
        return;
    }*/
    for(int i=0;i<A.size();i++)
    {
        int x=A[i];
        int nxt=0;
        if(i+1<A.size())
            nxt=A[i+1];
        vecini[x].push_back(nxt);
    }
    C[0]=A[0];
    for(int i=1;i<=M;i++)
    {
        if(vecini[i].empty())
        {
            C[i]=0;
            continue;
        }
        else
        {
            v=vecini[i];
            C[i]=plsmake();
        }
    }
    for(int i=1;i<=s;i++)
    {
        X.push_back(lft[i]);
        Y.push_back(rgt[i]);
    }
    /*for(int i=0;i<C.size();i++)
        cout<<C[i]<<' ';
    cout<<'\n';
    for(int i=1;i<=s;i++)
        cout<<-i<<' '<<X[i-1]<<' '<<Y[i-1]<<'\n';*/
    answer(C,X,Y);
}

Compilation message

doll.cpp: In function 'int plsmake()':
doll.cpp:69:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for(int i=0;i<ord.size();i++)
      |                 ~^~~~~~~~~~~
doll.cpp:73:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         if(i+1<v.size())
      |            ~~~^~~~~~~~~
doll.cpp:81:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         if(i+1==ord.size())
      |            ~~~^~~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:129:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |     for(int i=0;i<A.size();i++)
      |                 ~^~~~~~~~~
doll.cpp:133:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |         if(i+1<A.size())
      |            ~~~^~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3676 KB Output is correct
2 Correct 23 ms 8028 KB Output is correct
3 Correct 16 ms 7516 KB Output is correct
4 Correct 1 ms 3932 KB Output is correct
5 Correct 8 ms 5208 KB Output is correct
6 Correct 24 ms 9604 KB Output is correct
7 Correct 1 ms 3676 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3676 KB Output is correct
2 Correct 23 ms 8028 KB Output is correct
3 Correct 16 ms 7516 KB Output is correct
4 Correct 1 ms 3932 KB Output is correct
5 Correct 8 ms 5208 KB Output is correct
6 Correct 24 ms 9604 KB Output is correct
7 Correct 1 ms 3676 KB Output is correct
8 Correct 34 ms 14852 KB Output is correct
9 Correct 37 ms 15256 KB Output is correct
10 Correct 58 ms 18628 KB Output is correct
11 Correct 2 ms 5724 KB Output is correct
12 Correct 1 ms 5720 KB Output is correct
13 Correct 1 ms 5832 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3676 KB Output is correct
2 Correct 23 ms 8028 KB Output is correct
3 Correct 16 ms 7516 KB Output is correct
4 Correct 1 ms 3932 KB Output is correct
5 Correct 8 ms 5208 KB Output is correct
6 Correct 24 ms 9604 KB Output is correct
7 Correct 1 ms 3676 KB Output is correct
8 Correct 34 ms 14852 KB Output is correct
9 Correct 37 ms 15256 KB Output is correct
10 Correct 58 ms 18628 KB Output is correct
11 Correct 2 ms 5724 KB Output is correct
12 Correct 1 ms 5720 KB Output is correct
13 Correct 1 ms 5832 KB Output is correct
14 Correct 72 ms 20900 KB Output is correct
15 Correct 36 ms 14492 KB Output is correct
16 Correct 57 ms 18004 KB Output is correct
17 Correct 2 ms 5732 KB Output is correct
18 Correct 1 ms 5724 KB Output is correct
19 Correct 2 ms 5916 KB Output is correct
20 Correct 62 ms 19668 KB Output is correct
21 Correct 1 ms 5724 KB Output is correct
22 Correct 1 ms 5724 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 5720 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 5724 KB Output is partially correct
2 Correct 59 ms 15980 KB Output is correct
3 Partially correct 105 ms 22244 KB Output is partially correct
4 Partially correct 113 ms 23084 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 5724 KB Output is partially correct
2 Correct 59 ms 15980 KB Output is correct
3 Partially correct 105 ms 22244 KB Output is partially correct
4 Partially correct 113 ms 23084 KB Output is partially correct
5 Partially correct 78 ms 23572 KB Output is partially correct
6 Partially correct 87 ms 27048 KB Output is partially correct
7 Partially correct 82 ms 26552 KB Output is partially correct
8 Partially correct 85 ms 27848 KB Output is partially correct
9 Partially correct 113 ms 22008 KB Output is partially correct
10 Partially correct 132 ms 29616 KB Output is partially correct
11 Partially correct 107 ms 28440 KB Output is partially correct
12 Partially correct 65 ms 20352 KB Output is partially correct
13 Partially correct 60 ms 19208 KB Output is partially correct
14 Partially correct 54 ms 18804 KB Output is partially correct
15 Partially correct 57 ms 18132 KB Output is partially correct
16 Partially correct 4 ms 6236 KB Output is partially correct
17 Partially correct 60 ms 17592 KB Output is partially correct
18 Partially correct 55 ms 17644 KB Output is partially correct
19 Partially correct 59 ms 18208 KB Output is partially correct
20 Partially correct 70 ms 21428 KB Output is partially correct
21 Partially correct 90 ms 26112 KB Output is partially correct
22 Partially correct 60 ms 20516 KB Output is partially correct