oj.uz

Submission #880546

# Submission time Handle Problem Language Result Execution time Memory
880546 2023-11-29T16:02:36 Z andrei_boaca Mechanical Doll (IOI18_doll) C++17
72 / 100
 124 ms 29636 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]=A[0];
        if(n==1)
        {
            C[1]=0;
            answer(C,X,Y);
            return;
        }
        if(n==2)
        {
            C[1]=-1;
            X.push_back(1);
            Y.push_back(0);
            answer(C,X,Y);
            return;
        }
        C[1]=-1;
        vector<int> bits;
        n--;
        int aux=n;
        while(aux!=0)
        {
            bits.push_back(aux%2);
            aux/=2;
        }
        reverse(bits.begin(),bits.end());
        for(int i=0;i<bits.size();i++)
        {
            s++;
            if(bits[i]==1)
                lft[s]=1;
            else
                lft[s]=-1;
            if(i+1<bits.size())
                rgt[s]=-(s+1);
            else
                rgt[s]=0;
        }
        for(int i=1;i<=s;i++)
        {
            X.push_back(lft[i]);
            Y.push_back(rgt[i]);
        }
        answer(C,X,Y);
        return;
    }
    if(n==16)
    {
        C[0]=A[0];
        for(int i=1;i<A.size();i++)
            v.push_back(A[i]);
        v.push_back(0);
        int c=plsmake();
        for(int i=1;i<=M;i++)
            C[i]=c;
        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:127:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |         for(int i=0;i<bits.size();i++)
      |                     ~^~~~~~~~~~~~
doll.cpp:134:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |             if(i+1<bits.size())
      |                ~~~^~~~~~~~~~~~
doll.cpp:150:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |         for(int i=1;i<A.size();i++)
      |                     ~^~~~~~~~~
doll.cpp:164:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |     for(int i=0;i<A.size();i++)
      |                 ~^~~~~~~~~
doll.cpp:168:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |         if(i+1<A.size())
      |            ~~~^~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3676 KB Output is correct
2 Correct 18 ms 7924 KB Output is correct
3 Correct 16 ms 7512 KB Output is correct
4 Correct 1 ms 5724 KB Output is correct
5 Correct 9 ms 7056 KB Output is correct
6 Correct 22 ms 9564 KB Output is correct
7 Correct 1 ms 3672 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3676 KB Output is correct
2 Correct 18 ms 7924 KB Output is correct
3 Correct 16 ms 7512 KB Output is correct
4 Correct 1 ms 5724 KB Output is correct
5 Correct 9 ms 7056 KB Output is correct
6 Correct 22 ms 9564 KB Output is correct
7 Correct 1 ms 3672 KB Output is correct
8 Correct 37 ms 14992 KB Output is correct
9 Correct 37 ms 15276 KB Output is correct
10 Correct 59 ms 18576 KB Output is correct
11 Correct 2 ms 5724 KB Output is correct
12 Correct 1 ms 5724 KB Output is correct
13 Correct 1 ms 3676 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3676 KB Output is correct
2 Correct 18 ms 7924 KB Output is correct
3 Correct 16 ms 7512 KB Output is correct
4 Correct 1 ms 5724 KB Output is correct
5 Correct 9 ms 7056 KB Output is correct
6 Correct 22 ms 9564 KB Output is correct
7 Correct 1 ms 3672 KB Output is correct
8 Correct 37 ms 14992 KB Output is correct
9 Correct 37 ms 15276 KB Output is correct
10 Correct 59 ms 18576 KB Output is correct
11 Correct 2 ms 5724 KB Output is correct
12 Correct 1 ms 5724 KB Output is correct
13 Correct 1 ms 3676 KB Output is correct
14 Correct 70 ms 20720 KB Output is correct
15 Correct 38 ms 14684 KB Output is correct
16 Correct 57 ms 18080 KB Output is correct
17 Correct 1 ms 5720 KB Output is correct
18 Correct 1 ms 5720 KB Output is correct
19 Correct 2 ms 5720 KB Output is correct
20 Correct 63 ms 19612 KB Output is correct
21 Correct 2 ms 5724 KB Output is correct
22 Correct 1 ms 5724 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5920 KB Output is correct
2 Correct 11 ms 7768 KB Output is correct
3 Correct 11 ms 7768 KB Output is correct
4 Correct 16 ms 8792 KB Output is correct

Subtask #6
28.0000000448 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5920 KB Output is correct
2 Correct 11 ms 7768 KB Output is correct
3 Correct 11 ms 7768 KB Output is correct
4 Correct 16 ms 8792 KB Output is correct
5 Partially correct 85 ms 23568 KB Output is partially correct
6 Partially correct 92 ms 27060 KB Output is partially correct
7 Partially correct 88 ms 26724 KB Output is partially correct
8 Partially correct 92 ms 28000 KB Output is partially correct
9 Partially correct 94 ms 22012 KB Output is partially correct
10 Partially correct 124 ms 29636 KB Output is partially correct
11 Partially correct 109 ms 28476 KB Output is partially correct
12 Partially correct 69 ms 20220 KB Output is partially correct
13 Partially correct 61 ms 19128 KB Output is partially correct
14 Partially correct 57 ms 18800 KB Output is partially correct
15 Partially correct 58 ms 17944 KB Output is partially correct
16 Partially correct 3 ms 8536 KB Output is partially correct
17 Partially correct 49 ms 17648 KB Output is partially correct
18 Partially correct 58 ms 17748 KB Output is partially correct
19 Partially correct 51 ms 18276 KB Output is partially correct
20 Partially correct 73 ms 21332 KB Output is partially correct
21 Partially correct 95 ms 26192 KB Output is partially correct
22 Partially correct 67 ms 20712 KB Output is partially correct